sequential search
sequential search in unsorted array
stop if item is found or when we look all the items.
while (idx < length AND NOT found)
if arr(idx) equals item
set found to True
else
idx += 1
sequential search in sorted array
stop if item is found or when we look all the items(if a(idx) is larger than item)
else if(arr(idx) > item)
idx = length - stop
binary search
find the item at the middle and eliminates half of items
stop if item is found or when we look all the items
3개인 경우를 생각하면 first == right 인 경우에도 한번더 해야함
left = 0 right = length - 1
mid = (left + right) / 2
while ( first <= right AND NOT found){
if a(mid) == item
found = true
else if a(mid) > item
right = mid - 1
else
left = mid + 1
sorting
selection sort
continues
while ( unsorted < length - 1) Not sorted Yet
1.Find smallest unsorted item
min = a(unsorted)
i = unsorted + 1
while(i < length)
if(a(i) < a(minIdx))
minIdx = i
i += 1
-
Swap unsorted with smallest
temp = a(unsorted)
a(unsorted) = a(minIdx)
a(minIdx) = temp -
unsorted += 1
Bubble sort
continues until sort is done
- Find the next item and Put it into its proper place
starting with last list element, compare pairs of elements,
swap if bottom is smaller than above
swap = true
while(unsorted < length -1 AND swap)
set swap to False
Bubble up the smallest item in unsorted part
unsorted += 1
bubble up {
while i > unsorted + 1
if ( arr(i) < arr(i-1))
swap arr(i),arr(i-1)
swap to true
i += 1
Insertion sort
item being added to sorted part, by bubble up
마지막 1 원소가 남았을때 앞의 정렬방식처럼 끝난것이 아님, 정렬해야할 원소를 나타내는 unsorted가 아닌 current
current = 1
while current < length
i = current
while i > 0 AND NOT placeFound
if a(i) < a(i-1)
swap ai ai-1
i = i -1
else
placeFound = True
current += 1
