Data Structure: sorting (basic)
Tags: datastructure, muict
Published: 2018-09-13 03:56:28

---
title: Data Structure: sorting (basic)
published: true
description: The sorting algorithms I'm covering in the article include bubble sort, selection sort, and insertion sort. 
tags: Data structure, MUICT
---
Sorting basically means to arrange the data in a certain order, so it's easier for us to use those data. In this post, I'll talk about some basic sorting algorithms; bubble sort, selection sort, and insertion sort.

##### Sorting Algorithms and their Complexity

| Algorithm | Complexity |
|----- | -------|
| Bubble Sort | O(n<sup>2</sup>) |
| Selection Sort | O(n<sup>2</sup>) |
| Insertion Sort | O(n<sup>2</sup>)|
| Shell Sort | O(n<sup>2</sup>) |
| Quick Sort | O(n<sup>2</sup>) |
| Radix Sort | O(nk) |
| Heap Sort | O(nlog(n)) |
| Merge Sort | O(nlog(n)) |

Before we head to the main contents, I would like to recommend a <a href="https://visualgo.net/en/sorting">website</a> that helps visualize how all these sorting algorithms work. (P.S. It helps with other stuffs too like visualizing hash table, binary heap, etc.). And <a href="https://www.toptal.com/developers/sorting-algorithms">this one</a> is helpful, too!

## Bubble Sort
In bubble sort we compare 2 items at a time, and we either swap them or move on to compare the next pair. It is infamously slow, but it's conceptually the _simplest_ of the sorting algorithm.
<a href="https://medium.com/karuna-sehgal/an-introduction-to-bubble-sort-d85273acfcd8">![](https://thepracticaldev.s3.amazonaws.com/i/g9h8bymai7xlv92jm8jl.png)</a>

A pseudocode of how it works to sort an array of size _n_
```text
1. Repeat i) to ii) for n times
    i) Compare the leftmost element in array with the next element
        a. If the leftmost element is bigger, swap them
        b. Else, go to 2.
    ii) Move to next position, set that element to be the leftmost element. Is there next element?
        a. Yes, go back to i)
        b. No, go back to 1.
2. Done
```
And here's a java code of bubble sort
```java
public void bubbleSort() {
    int out, in, temp;
    int[] a = new int[nElems];      // nElems is the number of elements we'll input later ^^||
    for(out=nElems-1; out>1; out--) {  
        for(in=0; in<out; in++) {
            if( a[in] > a[in+1] ) { // out of order?
                temp = a[in];       // swap them
                a[in] = a[in+1];
                a[in+1] = temp;
            }
        }
    }
}
```
#### Efficiency of Bubble sort
- comparison operations:

    > for N items: (N-1) + (N-2) + (N-3) + ... + 1
    >              = N*(N-1)/2
    >              ≈ N<sup>2</sup>/2

- swap operations:

    > usually less than comparison operations
    > ≈ N<sup>2</sup>/4

- which means its complexity ≈ O(N<sup>2</sup>), quite slow

## Selection Sort
In selection sort, we move along the data and select the _smallest_ item, swap the selected item to the position 0, and so on.
<a href="http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/09/array-sorting.html">![](https://thepracticaldev.s3.amazonaws.com/i/tw0f2aj5wkavn3fkofbv.gif)</a>
A pseudocode for an array of size _n_
```
1. Repeat i) to ii) for (n-1) rounds
    i) Go through every unsorted element
    ii) Pick the smallest one and swap with element at the first position (but next to those already been sorted)
2. Done 
```

A java code for selection sort
```java
public void selectionSort() {
    int out, in, min, temp;
    int[] a = new int[nElems];        // nElems is the number of elements we'll input later ^^||
    for(out=0; out<nElems-1; out++) {
        min = out;
        for(in = out+1; in<nElems; in++) {
            if(a[in] < a[min]) {      // if min is greater,
                min = in;             // we have a new min
                temp = a[out];        // swap 'em
                a[out] = a[min];
                a[min] = temp;
            }
        }
    }
}
```

#### Efficiency of Selection sort
- comparison operations:
    
    > the same as bubble sort
    > ≈ N<sup>2</sup>/2

- swap operations:

    > usually less than N

- thus we get O(N<sup>2</sup>); slow :/

## Insertion Sort
We divide the data into _2 lists_ (sorted and unsorted). In each iteration, the first element of the unsorted list is inserted at appropriate position into the sorted list.
<a href="http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/09/array-sorting.html">![](https://thepracticaldev.s3.amazonaws.com/i/tweu6pwc1n2iqkyk57fx.gif)</a>
pseudocode
```text
1. Repeat i) and ii) for (n-1) rounds
    i) insert the first unsorted element, to the sorted
    ii) compare the newly inserted element to all the sorted, and put it in place
2. Done
```

java code!
```java
public void insertionSort() {
    int in, out;
    int[] a = new int[nElems];         // nElems is the number of elements we'll input later ^^||
    for(out=1; out<nElems; out++) {    // out is dividing line
        long temp = a[out];            // remove marked item
        in = out;                      // start shifts at out
        while(in>0 && a[in-1]>=temp) { // until one is smaller,
            a[in] = a[in-1];           // shift item to right
            --in;                      // go left one position
        }
        a[in] = temp; // insert marked item
    }
} 
```

#### Efficiency of Selection sort
- comparison operations:

    > N*(N-1)/4
    > ≈ N<sup>2</sup>/4

- copy operations:

    > usually similar to comparison operations

- its complexity ≈ O(N<sup>2</sup>); still slow..
- If the data is sorted, the algorithm runs in almost O(N).
- If the data is in reverse order, it runs pretty much slow like the bubble sort


# Comparing the 3 simple sorts
They require only their initial data array plus a little extra memory, but all their algorithms execute in O(N<sup>2</sup>) time.

- The **bubble sort** is simple, but the least efficient. It is practical if the amount of data is small
- The **selection sort** minimizes the number of swaps, but the
number of comparisons is still high
- The **insertion sort** is the most versatile of the three, and is
the best in most situations, assuming the amount of data is small or the data is almost sorted.