imrinzzzz

Posted on

# Data Structure: sorting (basic)

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(n2)
Selection Sort O(n2)
Insertion Sort O(n2)
Shell Sort O(n2)
Quick Sort O(n2)
Heap Sort O(nlog(n))
Merge Sort O(nlog(n))

Before we head to the main contents, I would like to recommend a website 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 this one 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 pseudocode of how it works to sort an array of size n

``````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

``````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
≈ N2/2

• swap operations:

usually less than comparison operations
≈ N2/4

• which means its complexity ≈ O(N2), 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 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

``````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
≈ N2/2

• swap operations:

usually less than N

• thus we get O(N2); 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.

pseudocode

``````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!

``````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
≈ N2/4

• copy operations:

usually similar to comparison operations

• its complexity ≈ O(N2); 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(N2) 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.