Sorting Algorithm

Bubble,Exchange,Selection,Insertion,Shell Sort Implementation

package sort;

import java.util.Arrays;

public class ManySort {

// bubble sort

public static void bubbleSort(Integer[] S) {

int n = S.length;

int temp;

for (int i = 0; i < n; i++) {

boolean exchanged = false;

for (int j = 1; j <= n - 1; j++) {

if (S[j] < S[j - 1]) { // then exchange

exchanged = true;

temp = S[j];

S[j] = S[j - 1];

S[j - 1] = temp;

}

}

if (!exchanged)

return; // no exchange occurred

}

}

// exchange sort

public static void exchangeSort(Integer[] S) {

int n = S.length;

int temp;

for (int i = 0; i < n - 1; i++) {

for (int j = i + 1; j < n; j++) {

if (S[j] < S[i]) { // then exchange

temp = S[j];

S[j] = S[i];

S[i] = temp;

}

}

}

}

// selectionSort - for each pass, pick the next smallest item's index

public static void selectionSort(Integer[] S) {

int n = S.length;

int temp, smallest;

for (int i = 0; i < n - 1; i++) {

smallest = i;

for (int j = i + 1; j < n; j++) {

if (S[j] < S[smallest])

smallest = j;

}

// now exchange S[i] and S[smallest]

temp = S[i];

S[i] = S[smallest];

S[smallest] = temp;

}

}

// insertion sort

public static void insertionSort(Integer[] S) {

int n = S.length;

for (int j = 1; j < n; j++) {

int key = S[j];

int i = j - 1;

while ((i >= 0) && (S[i] > key)) {

S[i + 1] = S[i];

i--;

}

S[i + 1] = key;

}

}

public static void shellSort(Integer[] S) {

int gap, gap_max = 10, n = S.length;

for (int k = gap_max; k > 0; k--) {

// gap의 사이즈는???

gap = (int) Math.pow(2, k) - 1;

// gap의 크기만큼 증감하는 인덱스 (삽입정렬)

for (int j = 1; j < n; j += gap) {

int key = S[j];

int i = j - gap;

while ((i >= 0) && (S[i] > key)) {

S[i + gap] = S[i];

i -= gap;

}

S[i + gap] = key;

}

}

}

public static void main(String[] args) {

long startTime, endTime, timeDiffMilli, timeDiffSec;

int numberOfInts = 0;

long shell = 0, insert = 0, select = 0, bubble = 0, exc = 0;

for (int i = 6; i < 7; i++) {

shell = 0;

insert = 0;

select = 0;

bubble = 0;

exc = 0;

for (int k = 0; k < 10; k++) {

numberOfInts = (int) Math.pow(10, i);

Integer arrInts[] = IntegerGenerator.generate(numberOfInts);

Integer[] sorted = new Integer[numberOfInts];

System.arraycopy(arrInts, 0, sorted, 0, numberOfInts);

Arrays.sort(sorted); // use Java's default sorter

System.out.println("For " + numberOfInts + " integers");

Integer[] S = new Integer[numberOfInts];

startTime = System.currentTimeMillis();

System.arraycopy(arrInts, 0, S, 0, numberOfInts);

shellSort(S);

assert (Arrays.equals(sorted, S));

endTime = System.currentTimeMillis();

timeDiffMilli = endTime - startTime;

timeDiffSec = timeDiffMilli / 1000L;

// shell += timeDiffMilli;

shell += timeDiffSec;

System.out.println("  Shell: time diff(milli) = "

+ timeDiffMilli + " diff(sec) = " + timeDiffSec);

// startTime = System.currentTimeMillis();

// System.arraycopy(arrInts, 0, S, 0, numberOfInts);

// bubbleSort(S);

// assert (Arrays.equals(sorted, S));

// endTime = System.currentTimeMillis();

// timeDiffMilli = endTime - startTime;

// timeDiffSec = timeDiffMilli / 1000L;

// bubble += timeDiffMilli;

// System.out.println("  Bubble: time diff(milli) = "

// + timeDiffMilli + " diff(sec) = " + timeDiffSec);

//

// startTime = System.currentTimeMillis();

// System.arraycopy(arrInts, 0, S, 0, numberOfInts);

// exchangeSort(S);

// assert (Arrays.equals(sorted, S));

// endTime = System.currentTimeMillis();

// timeDiffMilli = endTime - startTime;

// timeDiffSec = timeDiffMilli / 1000L;

// exc += timeDiffMilli;

// System.out.println("  Exchange: time diff(milli) = "

// + timeDiffMilli + " diff(sec) = " + timeDiffSec);

startTime = System.currentTimeMillis();

System.arraycopy(arrInts, 0, S, 0, numberOfInts);

selectionSort(S);

assert (Arrays.equals(sorted, S));

endTime = System.currentTimeMillis();

timeDiffMilli = endTime - startTime;

timeDiffSec = timeDiffMilli / 1000L;

// select += timeDiffMilli;

select += timeDiffSec;

System.out.println("  Selection: time diff(milli) = "

+ timeDiffMilli + " diff(sec) = " + timeDiffSec);

startTime = System.currentTimeMillis();

System.arraycopy(arrInts, 0, S, 0, numberOfInts);

insertionSort(S);

assert (Arrays.equals(sorted, S));

endTime = System.currentTimeMillis();

timeDiffMilli = endTime - startTime;

timeDiffSec = timeDiffMilli / 1000L;

// insert += timeDiffMilli;

insert += timeDiffSec;

System.out.println("  Insertion: time diff(milli) = "

+ timeDiffMilli + " diff(sec) = " + timeDiffSec);

}

System.out.println("\n평균시간[" + numberOfInts + "]");

//System.out.println("Bubble : " + bubble / 10);

//System.out.println("Exchange : " + exc / 10);

System.out.println("Select : " + select / 10);

System.out.println("Insert : " + insert / 10);

System.out.println("Shell : " + shell / 10);

}

}

}

// Bubble Exchange Selection Insertion Shell

// 1000 4.8ms 3.8ms 0.9ms 1.0ms 0.8ms

//

// 10000 512.4ms 409.9ms 68.6ms 63.7ms 55.9ms

//

// 100000 81016.4ms 49907.8ms 8528.7ms 7570.3ms 6492.6ms

//

// 1000000 x x