Sorting part I
Bubble Sort: The algorithm gets its name from the way smaller elements "bubble" to the top of the list.
- How does it work?
by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.
- It’s no longer being used nowadays because it’s far too inefficient for lists having more than few element .. anyway, it’s the simplest sorting algorithm. So it could be used to introduce the sorting concept to beginners.
- Code:
void bubbleSort(int arr[])
{
int pass = 1, temp;
bool sorted = false;
while (!sorted && pass)
{
sorted = true;
for (int i = 0; i <= size - pass - 1; i++)
{
if (arr[i] > arr[i + 1])
{
temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
sorted = false;
}
}
pass++;
}
}
- How does it work?
1. Select the minimum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list (starting at the second position)
- Code:
void selectionSort(int arr[])
{
for (int i=0; i<=size-2; i++)
{
int min=i;
for (int j=i+1; j<=size-1; j++)
{
if(arr[min] > arr[j])
min=j;
}
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
}
- How does it work?
1. Suppose there exists a function called Insert designed to insert a value into a sorted sequence at the beginning of an array. (Like what we studied in static array based lists). It operates by beginning at the end of the sequence and shifting each element one place to the right until a suitable position is found for the new element. The function has the side effects as we know.
2. To perform an insertion sort, begin at the left-most element of the array and call Insert to insert each element encountered into its correct position. The ordered sequence into which the element is inserted is stored at the beginning of the array in the set of elements already examined. Each insertion overwrites a single value: the value being inserted.
- Code:
void insertionSort(int arr[])
{
for( int k=1; k<= size-1; k++)
{
int x=arr[k];
int i=k-1;
bool found=false;
while(!found && i>=0)
{
if(arr[i] > x)
{
int temp=arr[i];
arr[i]=arr[i+1];
arr[i+1]=temp;
i--;
}
else
found=true;
}
}
}
- How does it work?
1. arrange the list into a table and sort the columns (using an insertion sort).
2. Repeat this process, each time with smaller number of longer columns.
3. At the end, the table has only one column.
Example:
consider a list of numbers like [ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ].
we could visualize this as breaking the list of numbers into a table with 5 columns. This would look like this:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
We then sort each column, which gives us
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
When we read it back as a single list of numbers, we get [ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ]. Here, the 10 which was all the way at the end, has moved all the way to the beginning. This list is then again sorted using simple insertion sort.
- Code:
void shellSort(int arr[], int size)
{
int k=1;
do{
k=k*2+1;
}
while (k<=size);
do{
k=k/2; // no. of columns we’ll devide in
for(int i=k; i<=size-1; i++)
{
int j=i-k;
bool found=false;
while( !found && j>=0 ) //sort the col.
{
if( arr[j] > arr[j+k] )
{
int temp=arr[j];
arr[j]=arr[j+k];
arr[j+k]=temp;
j=j-k;
}
else
found=true;
}
}
}
while (k!=1);
}
time complixity of each algo :
| Name | Average Case | Worst Case | Memory Usage | method |
| Bubble |
|
|
| Swapping |
| Selection |
|
|
| selecting |
| Insertion |
|
|
| inserting |
| Shell | -- |
|
| inserting |
where ( n ) is the number of elements to be sorted.
As we can see, they’ll not be so fast for larger lists.
There’re more efficient algos to be used (like quickSort ..) . We’ll know about them later.
UVa related problems:
299 - Train Swapping
10327 - Flip Sort
And to see that any of these algos isn’t so quick. Try to solve this :)
A pdf file (recommended) could be downloaded from here