DS7 BASIC SORTING METHODS

Question 1

RULES

Answer 1

input: collection of items
each item has a key(not necessarily a literal one if arithmetical or alphabetical order)
output: reordered collection based on key

internal sorting(uses memory)
external sorting(uses hard drive or ssd)

Question 2

INSERTION SORT

Answer 2

loop on input data
on k iteration a[0]-a[k-1] is already sorted
we compare with the sorted list until we find the right place
sort() methods:
less() compares
exch() exchange places
compExch() exchange places on comparison

class ArraySortBasic{
~static boolean less(double v, double w){return v < w;}
~static void exch(double[] a, int i, int j){double t = a[i]; a[i] = a[j]; a[j]=t;}
~static void compExch(double[] a, int i, int j){
~~if(less(a[j], a[i])){exch()a, i, j);}}
~static void sort(double[] a int p, int r){
~~for(int i = p+1; i<=r; i++){
~~~for(int j = i; j> p; j–){
~~~~compExch(a, j-1, j);}}}
}

O(n^2) complexity

Question 3

STABLE AND UNSTABLE SORTING

Answer 3

refers to how the algorithm treats equally graded elements
stable: elements of the same grade appear in the same order when sorted and unsorted
ie. a-1, b-3, c-7, d-3, e-6, f-6 (unsorted)
a-1, b-3, d-3, e-6, f-6, c-7 (sorted)
order is maintained when values that the elements are compared based on are equal they stay in the same order as before sorting

Question 4

INDIRECT SORTING

Answer 4

instead of moving the items in the array we assign pointers and change where the pointers point ( in java we sort the reference and in c++ we sort the pointers)

Question 5

GENERALIZATION

Answer 5

separate the algorithm from the data and key types
use comparable (returns ints to signify order) or comparator (is a bit more customizable) interface in java
implements the less method using comparator or as part of specific class (if custom class is used)

this method is best for objects and not default types
usually sort the pointer/reference
lower cost than copying whole objects

Question 6

BUBBLE SORT

Answer 6

from right to left
carries the lowest graded element to the beginning of the structure

static void bubble(item[] a, int p, int r){
for (int i = p; i <r; i++){
for (int j = r; j>i; j–){compExch(a, j-1, j);}} }
O(n^2) complexity

Question 6

SELECTION SORT

Answer 6

find smaller
change place with the element in first index
do again but consider first index the next space
every time iteration is reduced by 1
it is similar to dividing the structure in sorted and unsorted where the sorted part increases in size linearly
in every iteration we scan second sub array and put the item in last spot of first subarray
O(n^2) complexity

static void selection(item [] a, int p, int r){
for (int i = p; i<r; i++){
int min = i
for (int j = i+1; j<=r; j++){
if(less(a[j], a[min])){
min = j;}}
exch(a, i, min);}}

Question 7

OPTIMIZING INSERTION SORT

Answer 7

how to optimize:
stop compExch when item is in the correct position
consecutive exch of same item is costly and inefficient
use guard element

static void insertion(item[] a, int p, int r){
int i;
//place smallest in first place as guard element
for (i = r; i>p; i–{compExch(a, i=1, i);}
for (i = p+2; i<=r; i++){
int j = i; item v = a[i];
while(less(v, [j-1]){
// move j-1
a[j] = a[j-1];
j–;}
a[j] = v;
}}
still O(n^2) but its faster

Question 8

NOTES ON PERFORMANCE

Answer 8

all are O(n^2) but they are not the same
-selection sort does only few exchanges and the amount does not depend on size of input
-bubble sort adaptive version checks if there was exchange in previous iteration
-bubble and insertion sort do better than selection sort in partly sorted data

Question 9

SORTING LISTS

Answer 9

-change pointers not nodes, the structure not the contents

-selection sort:
one unsorted and one sorted list
find largest value in unsorted list
put in first place of sorted list

private static Node maxv(Node h){
//returns node that is the previous of the max node found
for(Node t = h; t.next != null; t = t.next)
{if(h.next.item < t.next.item){h = t}}
return h;}

static Node sort(Node h){
// h is the input list head points to it
Node head = new Node(-1, h);
//out is the output list
Node out = null;
while(head.next != null){
//keep node before max
Node max = maxv(head);
//t is max node
Node t = max.next;
//remove t from unsorted list
max.next = t.next;
//this ones doesnt make sense probably wanna make the next filed null
t.next = out;
//put in head of list
out = t;}
return out;}

Question 10

COUNTING SORT

Answer 10

see: https://www.javatpoint.com/counting-sort