Orders a list by comparing each item with the next and swapping if they are out of order, repeating until a full pass is made with no swaps. Most inefficient sorting algorithm, but very easy to implement Not good on already ordered lists or big lists

Bubble sort in structured English

1. Start at first item 2. Compare current item with next 3. If in wrong position, swap them 4. Move to next item 5. Repeat from 2 until all unsorted items have been compared 6. If any items were swapped, repeat from step 1. Otherwise it is done

Inserts each item into its correct position in a data set one at a time Splits the list into two; a sorted list and an unsorted one Efficient on small data sets and already sorted ones, bad on large data sets

Insertion sort in structured English

1. Start at second item 2. Compare with next item to left 3. If next item >, move next item up one 4. Repeat from 2 until position of item to be inserted is found 5. Insert current item 6. Repeat from 2 with next item until all items are inserted

Insertion sort in pseudocode

For index = 1 TO items.Length: current = items[index] index2 = index While index2 > 0 AND items[index2 - 1] > current items[index2] = items[index2 - 1] index2 = index2 - 1] End while items[index2] = current End For

Data repeatedly halved until each item on own, then merge lists (in correct space) Divide + conquer algorithm Good on large data sets, but lots of memory Ideal for parallel processing Separate lists after split step can each be placed in a 2D list

Merge sort in structured English (merge step)

2start w/ first items in two adjacent lists 3Compare 4Insert lowest into new list, move to next item in list taken from 5Repeat 3+4 until all items from 1 list in new 1 6Add all items from other list 7Replace lists with 1 8Repeat from 2 till 1 list

Merge sort in structured English (split step)

1. Repeatedly divide each list in half until each item is in its own list

Compares items against pivot value from data, to determine position Good on any data sets, but especially good on large data sets Ideal for parallel processing where divide and conquer can be used Often used in real-time situations due to efficiency

Quicksort in structured English

1pointer to first + last item 2While first pointer != second pointer aIf items at pointers in wrong order, swap items + pointers bMore first pointer one towards second pointer 3Repeat from 1 to left of pointer 4Repeat from 1 to right of pointer

Help

Options

focusNode

Didn't know it?
click below

Knew it?
click below

Don't Know

Remaining cards (0)

Know

retry

shuffle

restart

0:00

Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

Sorting algs

1.3.1

Question	Answer
Bubble sort	Orders a list by comparing each item with the next and swapping if they are out of order, repeating until a full pass is made with no swaps. Most inefficient sorting algorithm, but very easy to implement Not good on already ordered lists or big lists
Bubble sort in structured English	1. Start at first item 2. Compare current item with next 3. If in wrong position, swap them 4. Move to next item 5. Repeat from 2 until all unsorted items have been compared 6. If any items were swapped, repeat from step 1. Otherwise it is done
Bubble sort in pseudocode
Insertion sort	Inserts each item into its correct position in a data set one at a time Splits the list into two; a sorted list and an unsorted one Efficient on small data sets and already sorted ones, bad on large data sets
Insertion sort in structured English	1. Start at second item 2. Compare with next item to left 3. If next item >, move next item up one 4. Repeat from 2 until position of item to be inserted is found 5. Insert current item 6. Repeat from 2 with next item until all items are inserted
Insertion sort in pseudocode	For index = 1 TO items.Length: current = items[index] index2 = index While index2 > 0 AND items[index2 - 1] > current items[index2] = items[index2 - 1] index2 = index2 - 1] End while items[index2] = current End For
Merge sort	Data repeatedly halved until each item on own, then merge lists (in correct space) Divide + conquer algorithm Good on large data sets, but lots of memory Ideal for parallel processing Separate lists after split step can each be placed in a 2D list
Merge sort in structured English (merge step)	2start w/ first items in two adjacent lists 3Compare 4Insert lowest into new list, move to next item in list taken from 5Repeat 3+4 until all items from 1 list in new 1 6Add all items from other list 7Replace lists with 1 8Repeat from 2 till 1 list
Merge sort in pseudocode (main code)
Merge sort in structured English (split step)	1. Repeatedly divide each list in half until each item is in its own list
Merge sort in pseudocode (merge function)
Quicksort	Compares items against pivot value from data, to determine position Good on any data sets, but especially good on large data sets Ideal for parallel processing where divide and conquer can be used Often used in real-time situations due to efficiency
Quicksort in structured English	1pointer to first + last item 2While first pointer != second pointer aIf items at pointers in wrong order, swap items + pointers bMore first pointer one towards second pointer 3Repeat from 1 to left of pointer 4Repeat from 1 to right of pointer
Quicksort in pseudocode

Created by: FlashCardFun!

"Know" box contains:
Time elapsed:
Retries: