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

 

1. Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
2. 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