• +1-617-874-1011 (US)
  • +44-117-230-1145 (UK)
Live Chat
Follow Us:

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).
  1. 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(n2) How many swaps?

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

  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(n2)

  • How many swaps?

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.
  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(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.

Resources

  • 24 x 7 Availability.
  • Trained and Certified Experts.
  • Deadline Guaranteed.
  • Plagiarism Free.
  • Privacy Guaranteed.
  • Free download.
  • Online help for all project.
  • Homework Help Services

Testimonials

Urgenthomework helped me with finance homework problems and taught math portion of my course as well. Initially, I used a tutor that taught me math course I felt that as if I was not getting the help I needed. With the help of Urgenthomework, I got precisely where I was weak: Sheryl. Read More