# Bubble sort, Insertion sort, Selection Sort

## Activity Outcomes:

This lab teaches you the following topics:

- How to sort the input data

__Introduction__

**Bubble Sort**

** **

Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.

**Algorithm**

** **

- Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
- If at least one swap has been done, repeat step

### Insertion Sort

** **

Insertion sort belongs to the O(n2) sorting algorithms. Unlike many sorting algorithms with quadratic complexity, it is actually applied in practice for sorting small arrays of data. For instance, it is used to improve quicksort routine. Some sources notice, that people use same algorithm ordering items, for example, hand of cards.

**Algorithm**

** **

Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into two parts – sorted one and unsorted one. At the beginning, sorted part contains **first element **of the array and unsorted one contains the rest. At every step, algorithm takes **first element **in the unsorted part and **inserts **it to the right place of the sorted one. When unsorted part becomes **empty**, algorithm *stops*.

### Selection Sort

** **

Selection sort is one of the O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Selection sort is notable for its programming simplicity and it can over perform other sorts in certain situations (see complexity analysis for more details).

**Algorithm**

** **

The idea of algorithm is quite simple. Array is imaginary divided into two parts – sorted one and unsorted one. At the beginning, sorted part is **empty**, while unsorted one contains **whole array**. *At every step, *algorithm finds **minimal element **in the unsorted part and adds it to the end of the sorted one. When unsorted part becomes **empty**, algorithm *stops*.

When algorithm sorts an array, it swaps first element of unsorted part with minimal element and then it is included to the sorted part. This implementation of selection sort in **not stable**.

In case of linked list is sorted, and, instead of swaps, minimal element is linked to the unsorted part, selection sort is **stable**.

__Lab Activities:__

## Activity 1:

**Write a function to sort array elements using bubble sort**

** **

## Solution:

## Activity 2:

**Write a function to sort array elements using insertion sort**

** **

## Solution:

Void insertionSort(int arr[], int length)

{

inti, j, tmp;

for (i = 1; i<length; i++)

{

j = i;

while (j> 0 &&arr[j – 1] >arr[j])

{

tmp = arr[j];

arr[j] = arr[j – 1];

arr[j – 1] = tmp;

j–;

}

}

}

## Activity 3:

**Write a function to sort array elements using selection sort**

** **

## Solution:

Related links

Single link list Stack AVL Trees Binary search Counting Sort

Doubly link list Queue Graphs Bubble Sort Radix sort

Circular link list Binary search tree Hashing Insertion Sort Bucket Sort

Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort

# At Cui tutorial, courses, past papers and final year projects

#tutorial #cui #pastpaper #courses