Searching and Sorting with Array

AlgoDS/Algorithm 2019. 9. 4. 21:12

1. Overview

Two array processing technique that are particularly common are searching and sorting. Searching here refers to finding an item in the array that meets some specified criterion. Sorting refers to rearranging all the items in the array into increasing or decreasing order.

2. Description

Sorting	Process	Big O
Selection Sort	Find the smallest value in A and put it in A[0] Find the second smallest value in A and put it in A[1] and so on(smallest or largest, depending on sorting order)	always O(N^2)
Insertion Sort	Put the first 2 items in a correct relative order Insert the 3rd in the correct place relative to the first 2 Insert the 4th item in the correct place relative to the first 3 and so on	O(N) on an already-sorted array O(N^2) on worst-case
Merge Sort	Recursively sort the first N/2 items Recursively sort the last N/2 items Merge using an auxiliary array	always O(N*log N)
Quick Sort	Choose a pivot value partition the array Left part has item <= pivot Right part has item >= pivot Recursively sort the left part Recursively sort the right part	O(N^2) on worst-case O(N*log N) on expected