Gruppe N+1 oppgavesett 9
Fra Hiofwiki
Oppgaver til uke 11 og 13 -- Søking og sortering AKA oppgavesett 9
Fra kapittel 11 i læreboka:
11.4
a)
Selection sort
90 8 7 56 123 235 9 1 653
1 8 7 56 123 235 9 90 653
1 7 8 56 123 235 9 90 653
1 7 8 9 123 235 56 90 653
1 7 8 9 56 235 123 90 653
1 7 8 9 56 90 123 235 653
b)
Insertion sort
90 8 7 56 123 235 9 1 653
8 90 7 56 123 235 9 1 653
7 8 90 56 123 235 9 1 653
7 8 56 90 123 235 9 1 653
7 8 56 90 123 235 9 1 653
7 8 56 90 123 235 9 1 653
7 8 9 56 90 123 235 1 653
1 7 8 9 56 90 123 235 653
1 7 8 9 56 90 123 235 653
c)
Bubble sort
90 8 7 56 123 235 9 1 653
8 7 56 90 123 9 1 235 653
7 8 56 90 9 1 123 235 653
7 8 56 9 1 90 123 235 653
7 8 9 1 56 90 123 235 653
7 8 1 9 56 90 123 235 653
1 7 8 9 56 90 123 235 653
d)
Quick sort
90 8 7 56 123 235 9 1 653
Velger 56 som partisjonselement
8 7 9 1 | 56 | 90 123 235 653
Velger 8 som partisjonselement
1 7 | 8 | 9
Velger 123 som partisjonselement
90 | 123 | 235 653
Deler på nytt på hver side av partisjonene
Setter sammen igjen:
1 7 8 9 56 90 123 235 653
e)
Merge sort
|90 8 7 56 123 235 9 1 653|
|90 8 7 56 123| |235 9 1 653|
|90 8 7| |56 123| |235 9| |1 635|
| 90 8| |7| | 56| | 123| |235| | 9| |1| |635|
|90| |8| |7| |56| |123| |235| |9| |1| |635|
---------------------------------------------------------------------------------------------------------
|90| |8| |7| |56| |123| |235| |9| |1| |635|
|90 8 | |7 56 123| |9 235| |1 635|
|7 8 56 90 123| |1 9 235 635|
|1 7 8 9 56 90 123 235 653|
11.5
Leter etter 235.
1 7 8 9 56 90 123 235 653
Sjekker først det midterste elementet, 56. Dette er ikke tallet vi leter etter, og siden 235 > 56, må vi lete videre i den andre halvdelen av lista.
1 7 8 9 56 90 123 235 653
Sjekker deretter det midterste elementet i den andre halvdel av lista, som vi her velger at er 235. Vi sjekker om dette er tallet vi leter etter, og det er det.
Programming Projects
11.1
public class bubbleSort<T extends Comparable<? super T>> {
public void bubbleSort (T[] data)
{
int position, scan;
T temp;
boolean sortert = true;
for (position = data.length - 1; position >= 0 && !sortert; position--)
{
sortert = true;
for (scan = 0; scan <= position - 1; scan++)
{
if (data[scan].compareTo(data[scan+1]) > 0)
{
/** Swap the values */
temp = data[scan];
data[scan] = data[scan + 1];
data[scan + 1] = temp;
sortert = false;
}
}
}
}
}
11.3
import java.io.IOException;
import java.util.Random;
public class sortTest{
public static int n;
public static final int
MAX_N = 15000000,
MAX_INSERTION = 100000,
MAX_QUICK = 15000000,
MAX_MERGE = 5000000,
MAX_SELECTION = 3000000;
public static int comps;
public static <T extends Comparable<? super T>> void selectionSort (T[] data)
{
int min;
T temp;
comps = 0;
for (int index = 0; index < data.length-1; index++)
{
min = index;
for (int scan = index+1; scan < data.length; scan++){
if (data[scan].compareTo(data[min])<0)
min = scan;
comps++;
}
/** Swap the values */
temp = data[min];
data[min] = data[index];
data[index] = temp;
}
}
public static <T extends Comparable<? super T>> void insertionSort (T[] data)
{
comps = 0;
for (int index = 1; index < data.length; index++)
{
T key = data[index];
int position = index;
/** Shift larger values to the right */
while (position > 0 && data[position-1].compareTo(key) > 0)
{
data[position] = data[position-1];
position--;
comps++;
}
data[position] = key;
}
}
public static <T extends Comparable<? super T>> void bubbleSort (T[] data)
{
int position, scan;
T temp;
comps = 0;
for (position = data.length - 1; position >= 0; position--)
{
for (scan = 0; scan <= position - 1; scan++)
{
if (data[scan].compareTo(data[scan+1]) > 0)
{
/** Swap the values */
temp = data[scan];
data[scan] = data[scan + 1];
data[scan + 1] = temp;
}
comps++;
}
}
}
public static <T extends Comparable<? super T>> void quickSort (T[] data, int min, int max)
{
int indexofpartition;
comps =0;
if (max - min > 0)
{
/** Create partitions */
indexofpartition = findPartition(data, min, max);
/** Sort the left side */
quickSort(data, min, indexofpartition - 1);
comps++;
/** Sort the right side */
quickSort(data, indexofpartition + 1, max);
comps++;
}
}
private static <T extends Comparable<? super T>> int findPartition (T[] data, int min, int max)
{
int left, right;
T temp, partitionelement;
partitionelement = data[min]; // use first element as partition
left = min;
right = max;
while (left<right)
{
/** search for an element that is > the partitionelement */
while (data[left].compareTo(partitionelement) <=0 &&
left < right)
left++;
/** search for an element that is < the partitionelement */
while (data[right].compareTo(partitionelement) > 0)
right--;
/** swap the elements */
if (left<right)
{
temp = data[left];
data[left] = data[right];
data[right] = temp;
}
}
/** move partition element to partition index*/
temp = data[min];
data[min] = data[right];
data[right] = temp;
return right;
}
public static <T extends Comparable<? super T>> void mergeSort(T[] data, int min, int max)
{
T[] temp;
int index1, left, right;
comps = 0;
/** return on list of length one */
if (min==max)
return;
/** find the length and the midpoint of the list */
int size = max - min + 1;
int pivot = (min + max) / 2;
temp = (T[])(new Comparable[size]);
mergeSort(data, min, pivot); // sort left half of list
mergeSort(data, pivot + 1, max); // sort right half of list
/** copy sorted data into workspace */
for (index1 = 0; index1 < size; index1++)
temp[index1] = data[min + index1];
/** merge the two sorted lists */
left = 0;
right = pivot - min + 1;
for (index1 = 0; index1 < size; index1++)
{
if (right <= max - min)
if (left <= pivot - min)
if (temp[left].compareTo(temp[right]) > 0)
data[index1 + min] = temp[right++];
else
data[index1 + min] = temp[left++];
else
data[index1 + min] = temp[right++];
else
data[index1 + min] = temp[left++];
comps++;
}
}
public static void main(String args[])
{
Integer[] data;
long time = 0;
Random r = new Random();
try
{
if (args.length != 1)
throw new IOException("Please provide one integer");
n = Integer.parseInt(args[0]);
if (n < 0 || n > MAX_N)
throw new IOException("Illegal value of n: " + n +
". Use 0 < " + n + " < " + MAX_N);
}
catch (Exception e)
{
System.err.println(e);
System.exit(1);
}
data = new Integer[n];
if (n <= MAX_INSERTION)
{
for (int i = 0; i < n; i++)
data[i] = r.nextInt(3 * n);
time = System.currentTimeMillis();
insertionSort(data);
time = System.currentTimeMillis() - time;
System.out.println();
System.out.println("Insertion sort: " + time/1000.0 + " s");
System.out.println("Number of comparisons:" + comps);
}
else
System.out.println("Insertion sort: " + "Too slow for large n");
if (n <= MAX_QUICK)
{
for (int i = 0; i < n; i++)
data[i] = r.nextInt(3 * n);
time = System.currentTimeMillis();
quickSort(data,0,n-1);
time = System.currentTimeMillis() - time;
System.out.println();
System.out.println("Shell sort : " + time/1000.0 + " s");
System.out.println("Number of comparisons:" + comps);
}
else
System.out.println("Quick sort : " + "Too slow for large n");
if (n <= MAX_MERGE)
{
for (int i = 0; i < n; i++)
data[i] = r.nextInt(3 * n);
time = System.currentTimeMillis();
mergeSort(data, 0, n-1);
time = System.currentTimeMillis() - time;
System.out.println();
System.out.println("Merge sort : " + time/1000.0 + " s");
System.out.println("Number of comparisons:" + comps);
}
else
System.out.println("Merge sort : " + "Too memory-intensive for large n");
for (int i = 0; i < n; i++)
data[i] = r.nextInt(3 * n);
time = System.currentTimeMillis();
quickSort(data, 0, n-1);
time = System.currentTimeMillis() - time;
System.out.println();
System.out.println("Quick sort : " + time/1000.0 + " s");
System.out.println("Number of comparisons:" + comps);
if (n <= MAX_SELECTION)
{
for (int i = 0; i < n; i++)
data[i] = r.nextInt(10000000);
time = System.currentTimeMillis();
selectionSort(data);
time = System.currentTimeMillis() - time;
System.out.println();
System.out.println("Selection sort : " + time/1000.0 + " s");
System.out.println("Number of comparisons:" + comps);
}
else
System.out.println("Selection sort : " + "Too memory-intensive for large n");
}
}
Oppgave 1
public class FletteSortLinkedList
{
public static class Node
{
int tall;
Node neste;
public Node(int s, Node neste)
{
tall = s;
this.neste = neste;
}
}
public Node partition(Node liste)
{
Node forward = liste;
Node liste2 = forward;
int i = 0;
while(forward != null)
{
forward = forward.neste;
if(forward != null && forward.neste == null)
{
Node temp = liste2.neste;
liste2.neste = null;
liste2 = temp;
break;
}
else if(i++ % 2 == 0)
liste2 = liste2.neste;
}
return liste2;
}
public Node sortList(Node liste)
{
Node newList = null;
Node help = null;
Node liste2 = partition(liste);
if(liste2 == null)
{
return liste;
}
else
{
//Sorterer nodene rekursivt
liste = sortList(liste);
liste2 = sortList(liste2);
while(liste != null && liste2 != null)
{
if(liste.tall < liste2.tall)
{
// Legger til fra liste
if(newList == null)
help = newList = liste;
else
{
help.neste = liste;
help = help.neste;
}
liste = liste.neste;
}
else
{
// Legger til fra liste2
if(newList == null)
help = newList = liste2;
else
{
help.neste = liste2;
help = help.neste;
}
liste2 = liste2.neste;
}
}
//Fortsetter når en av listene er tomme
while(liste == null && liste2 != null)
{
help.neste = liste2;
help = help.neste;
liste2 = liste2.neste;
}
while(liste2 == null && liste != null)
{
help.neste = liste;
help = help.neste;
liste = liste.neste;
}
}
return newList;
}
public static void main(String[] att)
{
FletteSortLinkedList fsll = new FletteSortLinkedList();
Node n4 = new Node(5, null);
Node n3 = new Node(4, n4);
Node n2 = new Node(3, n3);
Node n1 = new Node(2, n2);
Node n0 = new Node(1, n1);
Node sortert = fsll.sortList(n0) ;
while(sortert != null)
{
System.out.print(sortert.tall + " ");
sortert = sortert.neste;
}
}
}
Og så Lars sin (inspirert av Petter's)
public class FletteSortLinkedList
{
public static class Node
{
int tall;
Node neste;
public Node(int s, Node neste)
{
tall = s;
this.neste = neste;
}
}
public Node partition(Node liste)
{
Node forward = liste;
Node liste2 = forward;
int i = 0;
while(forward != null)
{
forward = forward.neste;
if(forward != null && forward.neste == null)
{
Node temp = liste2.neste;
liste2.neste = null;
liste2 = temp;
break;
}
else if(i++ % 2 == 0)
liste2 = liste2.neste;
}
return liste2;
}
public Node sortList(Node liste)
{
Node newList = null;
Node forward = null;
Node liste2 = partition(liste);
if(liste2 == null)
{
return liste;
}
else
{
//Sorterer nodene rekursivt
liste = sortList(liste);
liste2 = sortList(liste2);
Node help = null;
while(liste != null && liste2 != null)
{
help = null;
// Finner liste med minste element
if(liste.tall < liste2.tall)
{
help = liste;
liste = liste.neste;
}
else
{
help = liste2;
liste2 = liste2.neste;
}
// Legger til fra liste
if(newList == null)
forward = newList = help;
else
{
forward.neste = help;
forward = forward.neste;
}
}
//Fortsetter når en av listene er tomme
help = null;
if(liste != null)
help = liste;
else if(liste2 != null)
help = liste2;
while(help != null)
{
forward.neste = help;
forward = forward.neste;
help = help.neste;
}
}
return newList;
}
public static void main(String[] att)
{
FletteSortLinkedList fsll = new FletteSortLinkedList();
Node n4 = new Node(1, null);
Node n3 = new Node(4, n4);
Node n2 = new Node(6, n3);
Node n1 = new Node(2, n2);
Node n0 = new Node(9, n1);
Node sortert = fsll.sortList(n0) ;
while(sortert != null)
{
System.out.print(sortert.tall + " ");
sortert = sortert.neste;
}
}
}
