Design and analysis Algorithm
Sorting Algorithms
Sorting Algorithms
Sorting algorithm are algorithms that enable organizing a set of items in a specific
order.
Sorting is a sorting of a group of elements according to a specific value called a key
or field, either in an ascending or descending order.
The purpose of the Sorting is
Increase search efficiency of the algorithm
Types of Sorting Algorithms
There are two types of sorting algorithms and they are classified into
Internal sorting algorithms
external sorting algorithms
Internal sorting algorithms: The sort takes place inside the memory ,when the size
of data is not large
The Internal sorting algorithms are
Bubble sort
insertion sort
selection sort
Shell sort
Quick sort
Radix sort
Tree sort
Pointer sort
External Sorting:
Is The sorting that occurs out of memory, in secondary storage device when the
data is large.
These algorithms
• merge sort
• balance two way merge sort
• Divided and conquer merge sort
The main factors for selecting the sorting algorithm
Data size: If the size of the data is small, then select internal sort algorithm or
external algorithm.
Storage type: If in the main memory, then select the internal algorithm otherwise
external sort algorithms
Degree of sorting
Internal Sorting algorithm: Bubble Sort
The bubble sort algorithm is the simplest of the sorting algorithms and for that
reason is a good beginning for our exploration of sorting techniques.
The bubble sort works like this:
You start at the left end of the line and compare the two item in positions 0 and 1.
If the one on the left (in 0) is grater, you swap them. If the one on the right is
greater , you don’t do anything. Then you move over one position and compare the
kids in positions 1 and 2. Again, if the one on the left is greater, you swap them.
And so on until the list is sorting
the bubble sort work like this :
1. Compare between two items.
2. If the one on the left is grater than, swap them.
3. Move one position right.
The complexity time of bubble sort algorithm
Algorithm
Bubble_sort( int array[1..n]) E( T ) = 0
For i← 0 to n do E( T ) = N
For j← 0 to n-1 do E( T ) = N
If ( array[j] > array[j+1])
Temp=array[j+1]
E( T ) = 1 E( T ) = N-1
Array[j+1]=array[j]
Array[j]=temp
Total of E( T ) = 0 + N + N-1( N + 1 ) = 0 + N + 𝑁 2 + N – N -1 O(N) = 𝑁 2
Internal Sorting algorithm: Selection Sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place
comparison-based algorithm in which the list is divided into two parts, the sorted
part at the left end and the unsorted part at the right end. Initially, the sorted part
is empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the
leftmost element, and that element becomes a part of the sorted array. This process
continues moving unsorted array boundary by one element to the right.
This algorithm is not suitable for large data sets
Selection sort Algorithm
Step(1): set MIN to location 0
Step(2): search the minimum element in the list
Step(3): swap with value at location MIN
Step(4): increment MIN to point to next element
Step(5): repeat until list is sorted
Complexity Analysis of Selection Sort
1. k ← length [A]
2. for j ←1 to n-1
3. smallest ← j
4. for I ← j + 1 to k
Best Case Complexity: O(n2)
5. if A [i] < A [ smallest] Average Case Complexity: O(n2
Worst Case Complexity: O(n2),
6. then smallest ← i
In the selection sort algorithm, the time complexity is O(n2) in
7. exchange (A [j], A [smallest]) all three cases.
Internal Sorting algorithm: Insertion Sort
Insertion sort is a simple sorting algorithm that works the way we sort playing
cards in our hands.
How Insertion Sort Works?
Example: using insertion sort sorted this array
Insertion sort compares the first two elements.
It finds that both 14 and 33 are already in ascending order.
For now, 14 is in sorted sub-list.
Insertion sort moves ahead and compares 33 with 27.
And finds that 33 is not in the correct position
It swaps 33 with 27. It also checks with all the elements of sorted sub-list.
This process goes on until all the unsorted values are covered in a sorted sub-list.
The algorithm
Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Complexity Analysis of Insertion Sort
