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:
- Sequential Search, and
- Binary Search
- 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).
- Simple Sorting Algorithm
Sorting: is a process of reordering a list of items in either increasing or decreasing order.
- Simple sorting algorithms include:
- Simple sort ii. Bubble Sort iii. Selection Sort iv. Insertion Sort
- 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(n2) • How many swaps?
1+2+3+…+(n-1)= O(n2)
- Bubble sort
Algorithm:
- 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
- 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
- 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(n2)
1+2+3+…+(n-1)= O(n2)
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(n2) 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(n2).
- 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.
- 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(n2) at worst case, regardless of the method of insertion.
- Number of comparisons may vary depending on the insertion algorithm.
▪ O(n2) for shifting or swapping methods ▪ O(nlogn) for binary insertion sort.
Follow Us