Simple Sorting and Searching Algorithms

Simple Sorting and Searching Algorithms

Why do we study sorting and searching algorithms?

• These algorithms are the most common and useful tasks operated by computer system.
• Computers spend a lot of time searching and sorting Simple Searching algorithms

Searching:- is a process of finding an element in a list of items or determining that the item is not in the list.

• To keep things simple, we shall deal with a list of numbers.
• A search method looks for a key, arrives by parameter.
• By convention, the method will return the index of the element corresponding to the key or, if unsuccessful, the value -1
• There are two simple searching algorithms:
  1. Sequential Search, and
  2. Binary Search
  3. a) Sequential Searching (Linear) The most natural way of searching an item.
• Easy to understand and implement.

Algorithm:

• In a linear search, we start with top (beginning) of the list, and compare the element at top with the key
• If we have a match, the search terminates and the index number is returned
• If not, we go on the next element in the list
• If we reach the end of the list without finding a match, we return -1.

Implementation:

• Assume the size of the list is n.

int LinearSearch(int list[ ], int key)

{

index=-1;

for(int i=0; i<n; i++)

{ if(list[i]==key)

{

index=i;

break;

}

}

return index;

}

Complexity Analysis:

• Big-Oh of sequential searching ➔ How many comparisons are made in the worst case ? n
• O(n).

2. Simple Sorting Algorithm

Sorting: is a process of reordering a list of items in either increasing or decreasing order.

• Simple sorting algorithms include:

1. Simple sort ii. Bubble Sort iii. Selection Sort iv. Insertion Sort
2. Simple sort algorithm Algorithm:

• In simple sort algorithm the first element is compared with the second, third and all subsequent elements.
• If any one of the these other elements is less than the current first element then the first element is swapped with that element.
• The above steps are repeated with the second, third and all subsequent elements.

Implementation:

Void SimpleSort(int list[])

{

for(int i=0; i<=n-2;i++) for(int j=i+1; j<=n-1; j++) if(list[i] > list[j])

{ int temp; temp=list[i]; list[i]=list[j]; list[j]=temp;

} }

Complexity Analysis:

• Analysis involves number of comparisons and swaps.
• How many comparisons?

1+2+3+…+(n-1)= O(n²) • How many swaps?

1+2+3+…+(n-1)= O(n²)

1. Bubble sort

Algorithm:

1. Compare each element (except the last one) with its neighbor to the right
   • If they are out of order, swap them
   • This puts the largest element at the very end
   • The last element is now in the correct and final place
2. Compare each element (except the last two) with its neighbor to the right
   • If they are out of order, swap them
   • This puts the second largest element next to last
   • The last two elements are now in their correct and final places

• Compare each element (except the last three) with its neighbor to the right

1. Continue as above until you have no unsorted elements on the left

7 2 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8 2 7 8 5 4 2 7 5 4 8 2 5 4 7 8 2 4 5 7 8

2 7 8 5 4 2 5 7 4 8 2 4 5 7 8 (done)

2 7 5 8 4 2 5 4 7 8

2 7 5 4 8

Example of bubble sort

Implementation:

Void BubbleSort(int list[ ])

{ int temp; for (int i=n-2; i>=0; i--) { for(int j=0;j<=i; j++)

if (list[j] > list[j+1]) {

temp=list[j]; list[j])=list[j+1]; list[j+1]=temp;

}

}

}

Complexity Analysis:

• Analysis involves number of comparisons and swaps.
• How many comparisons?

1+2+3+…+(n-1)= O(n²)

• How many swaps?

1+2+3+…+(n-1)= O(n²)

III. Selection Sort Algorithm

• The selection sort algorithm is in many ways similar to simple sort algorithms.
• 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
• When unsorted part becomes empty, algorithm stops.

 

Implementation:

void selectionSort(int list[ ] ) { int minIndex, temp; for (int i = 0; i <= n - 2; i++) { minIndex = i;

for (j = i + 1; j <= n-1; j++) if (list[j] < list[minIndex]) minIndex = j;

if (minIndex != i) { temp = list[i]; list[i] = list[minIndex];

list[minIndex] = temp;

}

}

}

Complexity Analysis

• Selection sort stops, when unsorted part becomes empty.
• As we know, on every step number of unsorted elements decreased by one.
• Therefore, selection sort makes n-1 steps (n is number of elements in array) of outer loop, before stop.
• Every step of outer loop requires finding minimum in unsorted part. Summing up, (n - 1) + (n - 2) + ... + 1, results in O(n²) number of comparisons.
• Number of swaps may vary from zero (in case of sorted array) to n-1 (in case array was sorted in reversed order), which results in O(n) number of swaps.
• Overall algorithm complexity is O(n²).
• Fact, that selection sort requires n-1 number of swaps at most, makes it very efficient in situations, when write operation is significantly more expensive, than read operation.

1. Insertion Sort

Algorithm:

• Insertion sort algorithm somewhat resembles SelectionSort and Bubble 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.

Using binary search

• It is reasonable to use binary search algorithm to find a proper place for insertion.
• This variant of the insertion sort is called binary insertion sort.
• After position for insertion is found, algorithm shifts the part of the array and inserts the element.

C++ implementation

void InsertionSort(int list[])

{

for (int i = 1; i <= n-1; i++) {

for(int j = i;j>=1; j--) { if(list[j-1] > list[j])

{ int temp = list[j]; list[j] = list[j-1];

list[j-1] = temp;

}

else

break;

}

}

}

Complexity Analysis

• The complexity of insertion sorting is O(n) at best case of an already sorted array and O(n²) at worst case, regardless of the method of insertion.
• Number of comparisons may vary depending on the insertion algorithm.

▪ O(n²) for shifting or swapping methods ▪ O(nlogn) for binary insertion sort.