Sorting Algorithms

- Repeat
steps 2 and 3 as index
goes from 0 to SIZE-2.*k* - Find
the smallest array value in the index range
to SIZE – 1. Call the index where the smallest value is found*k*.*smallest* - Swap
the old value at position
with the value at*k**smallest.*

Big O (n^{2})

- Repeat
steps 2 and 3 as index
goes from SIZE-1 to 1.*k* - Find
the largest array value in the index range 0 to k. Call the index where the largest value
is found
.*largest* - Swap
the old value at position
with the value at*k**largest.*

Big O (n^{2})

- Repeat
steps 2-5 as index
**i**goes from 0 to SIZE – 1 or until you find that the array is sorted. - Assume the array is sorted.
- Repeat
steps 4-5 as index
**k**goes from 0 to SIZE – 1 –**i**. - On
each pass compare element at index
**k**and element**k**+ 1. - If the pair is in increasing order (or the values are identical) leave the values as they are.

Otherwise the pair is in decreasing order, so swap them. Now you know that the array was not sorted.

Best Case = Big O (n)

Worst Case = Big O (n^{2})

Average Case = Big O (n^{2})

Partition the array in two parts sorted and unsorted.

- Start
with the element at index 0 in the sorted portion and the rest of the
array in the unsorted portion. Set
to 1.*DividerIndex* - Repeat
steps 3-7 as
goes from 1 to SIZE-1.*DividerIndex* - Copy
the value at the divider index in to another variable (
*DividerValue**).* - Search
through the sorted portion until the
is greater than a given element.*DividerValue* - Move
the rest of the element in the sorted region to the right one position to
make room for the
. (There may not be any to move.)*DividerValue* - Place
in the position left open.*DividerValue* - Increment
the
.*DividerIndex*

Worst Case = Big O (n^{2})

Average Case = Big O (n^{2})

1.
Pick an item from the **list** and call it the pivot.

2.
Move all of the elements that are smaller than the
pivot into a **left-list** and all of
the items that are greater than the pivot into **right-list**.

3.
Recursively perform steps 1 & 2 on the **left-list** and **right-list**.

a.
When the **list**
contains only one item it is sorted and no further calls should be made to QuickSort.

4.
The sorted list including the **left-list, pivot item** & the **right-list** should be copied back into
the **list**. (This is the answer…aka.
sorted list.)