**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(n ^{2}) **•

**1+2+3+…+(n-1)= O(n ^{2})**

**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

__Implementation:__

**Void BubbleSort(int list[ ])**

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

**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**^{2}**)**

**How many swaps?**

**1+2+3+…+(n-1)= O(n**^{2}**)**

**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**^{2})**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**^{2}).**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**__Selection____Sort__**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*.

**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**^{2})**at worst case, regardless of the method of insertion.****Number of comparisons may vary depending on the insertion algorithm.**

▪ **O(n ^{2}) **

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

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

## Follow Us