Sorting and Searching

selection sorting: swap values to the front

• swaps every iteration: finishes swapping after n-1 passes (won’t need to swap last element)

• after nth pass, the first n elements are sorted

  • ex. 2 iterations, 1 and 2 elements are good)

• fewer swaps

for (int i = 0; i < array.length - 1; i++){      /when it gets to second to last, its all sorted
	int minIndex = i;                        
	for (int j = i+1; j < array.length; j++){              /find the min
		if (arr[j] < arr[minIndex]){
			min = j;
		}
	}
	int temp = arr[i];   /swaps arr[0] with the min    and arr[1] with next min ... so on
	arr[i] = arr[j];
	arr[j] = arr[i];
}

insertion sorting: move values to the left

• swaps every iteration: finishes swapping after n-1 passes

• after nth pass, the first n elements are sorted in respect to itself

  • not necessarily the final product

• best: sorted in increasing order

• worst: sorted in reverse order

• better for nearly finished sorted arrays

[5, 10, 9, 2]

j i

for (int i = 1; i < arr.length; i++){           /unsorted part
	int current = arr[i];
	int j = i - 1;                      /one less than
	while (j >= 0 && arr[j] > current){ /while not reach 0 and element b4 is bigger than current
		arr[i] = arr[j];           /the values will be right next to each other so swap
		j = j + 1;
	}
	arr[j + 1] = current;
}

Both are bad for a large list of elements

recursive sort: merge sort

• merge method

  • recursive calls break the array into half, of each half into its own sections

  • pair adjacent pairs of lists

• Con: creates a temporary array

• all cases have similar run times

• generally FASTER than selection/insertion

sequential searching: in order

• average: n/2 comparison

• best: key is in the first slot

• worst: key is in the last slot

binary search: divide and conquer

• key is not found: return -1

• generally faster: esp if sorted

• best: key is in the center

• worst: not in array or endpoint

  • if n elements is power of 2, 2^power = n

    • # of comparison: power + 1

  • if n is not power of 2, round it to number that could do 2^power

    • # of comparison: power