Simple Sorts

The first 3 sorting algorithms are fairly straight forward. They are all O($n^2$). They are also the easiest to understand. We will give a brief description of each below.

Bubble Sort

Bubble sort is called bubble sort because the algorithm repeatedly bubbles the largest item within the list to the back/end of the list.

Algorithm

1. start with first pair of numbers
2. compare them and if they are not correctly ordered, swap them
3. go through every pair in list doing the above 2 steps
4. repeat the above 3 steps n-1 times (ie go through entire array n-1 times) and you will sort the array

Animation

http://cathyatseneca.github.io/DSAnim/web/bubble.html

Implementation

Python

def bubble_sort(my_list):
    n = len(my_list)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if my_list[j] > my_list[j + 1]:
                my_list[j], my_list[j + 1] = my_list[j + 1], my_list[j]

C++

void bubbleSort(int arr[],int size){
    int tmp;                          /*used for swapping*/
    int i;
    int j;
    for (i=0; i<size-1; i++) {
        for (j=0; j<size-1-i; j++){
            int next = j+1;
            if (arr[next] < arr[j]) {          /* compare the two neighbors */
                tmp = arr[j];                   /* swap a[j] and a[j+1]      */
                arr[j] = arr[next];
                arr[next] = tmp;
            }
        }
    }
}

Selection Sort

Selection sort works by selecting the smallest value out of the unsorted part of the array and placing it at the back of the sorted part of the array.

Algorithm

1. find the smallest number in the between index 0 and n-1
2. swap it with the value at index 0
3. repeat above 2 steps each time, starting at one index higher than previous and swapping into that position

Animation

http://cathyatseneca.github.io/DSAnim/web/selection.html

Implementation

Python

def selection_sort(my_list):

    n = len(my_list)
    for i in range(n - 1):
        min_idx = i  # record the index of the smallest value,
                     # initialized with where the smallest value may be found
        for j in range(i + 1, n):              # go through list, 
            if my_list[j] < my_list[min_idx]:  # and every time we find a smaller value,
                min_idx = j                    # record its index (note how nothing has moved at this point.)


        if min_idx != i:
            my_list[min_idx], my_list[i] = my_list[i], my_list[min_idx]

C++

void selectionSort(int arr[],int size){
    int i,j;
    int min;  //index of smallest value in the unsorted array

    for(int i=0;i<size-1;i++){
        min=i;
        for(int j=i+1;j<size;j++){
            if(arr[j] < arr[min]){
                min=j;
            }
        }
        if(min!=i){
            int tmp=arr[min];
            arr[min]=arr[i];
            arr[i]=tmp;
        }
    }
}

Insertion Sort

Insertion sort is called insertion sort because the algorithm repeatedly inserts a value into the part of the array that is already sorted. It essentially chops the array into two pieces. The first piece is sorted, the second is not. We repeatedly take a value/number from the second piece and insert it into the already sorted first piece of the array.

Algorithm

1. start with the second value in the list (note that the first piece/portion of the list contains just the first value initially.)
2. put that value into a temporary variable. This makes it possible to move items into the spot the second value occupies at the time and this spot is now considered to be an empty spot in the sorted piece/portion of the array.
3. if, when compared with the last value in the first piece/portion of the list, the value in the temporary variable should go into the empty spot, put it in.
4. otherwise, move the last value in the sorted piece/portion part into the empty spot.
5. repeat steps 3 to 4 until the value in the tempprary variable is placed somewhere into the first sorted piece/portion of the array.
6. repeat steps 2 to 5 for every vakue in the second piece/portion/part of the array until all values are placed in the first part.

Animation

http://cathyatseneca.github.io/DSAnim/web/insertion.html

Implementation

Python

def insertion_sort(my_list):
    for i in range(1, len(my_list)):
        curr = my_list[i]  # store the first number in the unsorted part of
                           # of array into curr
        j = i
        while j > 0 and my_list[j - 1] > curr:       # this loop shifts value within sorted part of array
            my_list[j] = my_list[j - 1]              # to open a spot for curr
            j -= 1
        my_list[j] = curr

C++

void insertionSort(int arr[],int size){
    int curr;
    int i, j;
    for(i=1;i<size;i++){
        curr=arr[i];
        for(j=i;j>0 && arr[j-1] > curr;j--){
            arr[j]=arr[j-1];
        }
        arr[j]=curr;
    }
}