Bubble sort, Insertion sort, Selection Sort
This lab teaches you the following topics:
- How to sort the input data
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.
- 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 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.
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 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).
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.
Write a function to sort array elements using bubble sort
Write a function to sort array elements using insertion sort
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;
Write a function to sort array elements using selection sort
At Cui tutorial, courses, past papers and final year projects
#tutorial #cui #pastpaper #courses