-
Notifications
You must be signed in to change notification settings - Fork 0
/
SortingAlgorithms.cpp
82 lines (75 loc) · 2.14 KB
/
SortingAlgorithms.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
using namespace std;
void bubbleSort(int n /* size of the array */, int *array)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
if (array[i] < array[j])
swap(array[i], array[j]);
}
}
return;
}
void selectionSort(int n, int *array){
for(int i = 0; i < n-1; i++){
int min_index = i;
for (int j = i+1; j < n; j++){
if (array[j] < array[min_index]) min_index = j;
}
if (array[min_index] < array[i]) swap(array[i], array[min_index]);
}
}
void insertionSort(int n, int *array){
for (int i = 1; i < n; i++){
int current = array[i]; // Current Element
int j = i-1; // (Initially) Last element of the sorted subarray.
// Pushing the Sorted part of array.
while(j >= 0 && array[j] > current){
array[j+1] = array[j];
j--;
}
// Inserting the current element at its correct position.
array[j+1] = current;
}
}
int main()
{
/**
* Aproach To Sorting Algorithms.
*
* Bubble Sort - Repeatedly swap two numbers if in wrong order.
* Selection Sort - Repeatedly find the smallest element of the unsorted array and put it in the beginning.
* Insertion Sort - Repeatedly take element from unsorted subarray and insert in sorted subarray.
*
* Space Time Complexity of these Algorithms.
*
* Bubble Sort [Stable] ->
*
* Time Complexity - O(n^2)
* Space Complexity - O(1)
* Maximum Number of Swaps - O(n^2)
*
* Selection Sort [Unstable] ->
*
* Time Complexity - O(n^2)
* Space Complexity - O(1)
* Maximum Number Of Swaps - O(n)
*
* Insertion Sort [Stable] ->
*
* Time Complexity -> O(n^2) or bigOmega(n) <- Best Case.
* Space Complexity -> O(1)
*/
int mySampleArray[] = {5, 2, 8, 7, 9};
bubbleSort(5, mySampleArray);
selectionSort(5, mySampleArray);
insertionSort(5, mySampleArray);
// Printing the array.
for (int i = 0; i < 5; i++)
{
cout << mySampleArray[i] << " ";
}
return 0;
}