Sorting Algorithms

From MMAE

Here is a list of the sorting algorithms which are covered on the Foundation Exam, along with their respective time complexities.

Contents 1 Bubble Sort 1.1 Example 1.2 Time Complexities 2 Selection Sort 2.1 Time Complexities 2.2 Trace 2.3 Selection Sort in C 3 Other notable sorting algorithms

[edit] Bubble Sort

Pass 1: Bubble Sort works by continuously stepping through each element in the array, comparing it with the next element. If element X is greater than element X+1, then the two elements are swapped. It continues comparing until it reaches the end of the array. One iteration of bubble sort is complete.

Pass 2: After pass 1 has been excuted, it is safe to assume that the last element is in its correct location. The greatest element in the entire array will end up at the end of the list after the first pass. This means, that we can step through the array again, but this time we can ignore the last element of the array.

Pass N: We continue iterating through the array, each time ignoring the last element of the previous pass, and when only one element remains unsorted, the array is sorted and bubble sort terminates.

[edit] Example

(Bold indicates the element is sorted)

Unsorted Array:

9

6

4

8

2

3

7

1

Pass 1:

6

4

8

2

3

7

1

9

Pass 2:

4

6

2

3

7

1

8

9

Pass 3:

4

2

3

6

1

7

8

9

...

Pass N:

1

2

3

4

6

7

8

9

[edit] Time Complexities

Worst Case: O(n²)

Average Case: O(n²)

Best Case: O(n²)

[edit] Selection Sort

• The unsorted list is split into two, an empty sorted list and the rest of the elements in an unsorted list.
• The smallest value from the unsorted list is swapped with the first element of the unsorted list. The pointer for the sorted list is advanced to include this new value.
• This repeats until there is only on element left in the unsorted sublist.

[edit] Time Complexities

Worst Case: O(n²)

Average Case: O(n²)

Best Case: O(n²)

[edit] Trace

U - unsorted
S - sorted

9

6

4

3

1

Pass 1:

1	6	4	3	9
S	U

Pass 2:

1	4	6	3	9
	S	U

Pass 3:

1	4	6	3	9
		S	U

Pass 4:

1	4	3	6	9
			S	U

Pass 5:

1	4	3	6	9
				S	U

[edit] Selection Sort in C

void selectionSort(int array[], int size)
{
        int min;
        int minIndex;
        int i,j;
        int temp;

        for(i = 0; i<size; i++)
        {
                minIndex = i;
                min = array[i];

                //Find the next smallest value
                for(j = i; j<size; j++)
                {
                        if(min > array[j])
                        {
                                minIndex = j;
                                min = array[j];
                        }
                }
                //The swap
                temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
        }
}                                                                                                                     

[edit] Other notable sorting algorithms

Insertion sort 

simplest sort, worst case O(n²), O(n) for already sorted data

start with empty list; use linear search to find the correct position for each element

Heap sort 

most generally efficent, O(n log n) for all cases

insert all elements into an ordered heap and then remove them

quicksort 

quickest sort on average; average: O(n log n), worst case O(n²), best case O(n)

recursively subdivide list by picking a pivot element, and place everything less in one list and everything greater in the other list

radix sort

fastest / easiest sort to perform by a human ; O( n · k) but requires lots of memory

subdivide list into one list per digit value for the most significant digit; recursively repeat in each sublist for subsequent digits.