Quick sort(퀵 정렬)



원칙1: pivot을 고른다.(주로 첫번째 또는 마지막 값을 선정하는 편이다.)

원칙2: pivot값을 기준으로 작은쪽, 큰쪽으로 나누어 서로간의 swap으로 위치를 교환한다.(증가될 수 없는 배열이라고 가정....)

원칙3: swap이 끝나면 그 나눈 중심에 pivot을 두고 작은쪽, 큰쪽을 각각 퀵소트한다.



Best case: O(n

Average case: O()

Worst case: O() 


# 재귀함수로 구현한 Quick sort

public class QuickSort implements ISort {


    @Override

    public void sort(Comparable[] array) {

        quickSort(array, 0, array.length - 1);

    }


    private void quickSort(Comparable[] array, int startIndex, int endIndex) {

        if (startIndex >= endIndex) {

            return;

        }


        final Comparable pivot = array[startIndex];

        int left = startIndex + 1;

        int right = endIndex;


        do {

            while (array[left].compareTo(pivot) < 0 && left < endIndex) {

                left++;

            }

            while (array[right].compareTo(pivot) > 0 && startIndex < right) {

                right--;

            }


            if (left < right) {

                swap(array, left, right);

            }


        } while (left < right && left < endIndex && startIndex < right);

        swap(array, startIndex, right);


        quickSort(array, startIndex, right - 1);

        quickSort(array, right + 1, endIndex);

    }


    private void swap(Comparable[] array, int i, int j) {

        Comparable temp = array[i];

        array[i] = array[j];

        array[j] = temp;

    }

}


Reference:

- https://en.wikipedia.org/wiki/Quicksort


'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

Merge sort(병합 정렬)



원칙1: 2개가 될때까지 쪼갠다.

원칙2: 2개가 되면 서로 비교해서 자리를 바꾸거나 바꾸지 않는다.

원칙3: 이렇게 조각난 2개를 4개로, 4개를 8개로... 순서를 맞추어 병합한다.


Best case: O(n

Average case: O()

Worst case: O() : 



# 재귀함수로 구현한 Merge sort

public class MergeSort implements ISort {


    @Override

    public void sort(Comparable[] array) {

        mergeSort(array, 0, array.length - 1);

    }


    private void mergeSort(Comparable[] array, int startIndex, int endIndex) {

        if (endIndex - startIndex < 1) {

            return;

        }


        int middleIndex = (endIndex + startIndex) / 2;

        mergeSort(array, startIndex, middleIndex);

        mergeSort(array, middleIndex + 1, endIndex);


        merge(array, startIndex, middleIndex, endIndex);

    }


    private void merge(Comparable[] array, int startIndex, int middleIndex, int endIndex) {

        Comparable[] mergedArray = new Comparable[endIndex - startIndex + 1];

        int indexA = startIndex;

        int indexB = middleIndex + 1;


        for (int i = 0; i < mergedArray.length; i++) {

            if (indexB > endIndex || (indexA <= middleIndex && array[indexA].compareTo(array[indexB]) < 0)) {

                mergedArray[i] = array[indexA++];

            } else {

                mergedArray[i] = array[indexB++];

            }

        }


        for (int i = 0, j = startIndex; i < mergedArray.length; i++, j++) {

            array[j] = mergedArray[i];

        }

    }

}


Reference:

https://en.wikipedia.org/wiki/Merge_sort


'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

Selection sort(선택 정렬)




- 1원칙: i 위치에 채워질 최저/최대값을뒤에서 찾는다.

- 2원칙i보다 가장 작은수를 찾는다.

- 3원칙: 있다면 i 자리를 바꾼다.



Best case: O()  == Worst case: O() : 어차피 다 확인해야 한다. 


public class SelectionSort {


    public void sort(Comparable[] array) {

        for (int i = 0; i < array.length; i ++) {

            int lowestIndex = i;

            for (int j = i + 1; j < array.length; j++) {

                if (array[lowestIndex].compareTo(array[j]) > 0) {

                    lowestIndex = j;

                }

            }


            // swap

            if (i != lowestIndex) {

                Comparable temp = array[i];

                array[i] = array[lowestIndex];

                array[lowestIndex] = temp;

            }

        }

    }

}


Referenced from: https://en.wikipedia.org/wiki/Selection_sort

'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

Insertion sort(삽입 정렬)



- 1원칙: i의 앞쪽은 이미 정렬된 상태라고 가정(i는 1부터 시작하기에 가능)

- 2원칙: i의 위치에서 자기보다 앞에 있는 (j < i)를 하나씩 비교해보며 작을경우 뒤로 Shifting한다.

- 3원칙: shifting하고 남은 공간에 i에 있던 item을 삽입한다.



i의 앞쪽은 항상 정렬된 상태이고

Best case: O(: 정렬이 거의 다 되어있는 상태에서...

Worst case: O() : 역순정렬된 상태 일때...


public class InsertionSort {


    public void sort(Comparable[] array) {

        for (int i = 1; i < array.length; i++) {

            final Comparable currentItem = array[i];

            int insertPosition = i - 1;

            while (insertPosition >= 0 && currentItem.compareTo(array[insertPosition]) < 0) {

                array[insertPosition + 1] = array[insertPosition];

                insertPosition--;

            }


            insertPosition++;

            if (insertPosition < i) {

                array[insertPosition] = currentItem;

            }

        }

    }

}




Reference:

https://en.wikipedia.org/wiki/Insertion_sort

'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

Bubble sort(거품? 정렬)



- 1원칙: i, i +1의 자리를 비교하여 뒤의것이 작다면 자리를 교환한다.

- 2원칙: 0 ~ n -1 이렇게 n개까지 돌리고 교환된 적이 있다면 다시 0부터 돌린다.(loop)

          loop: 앞이나 뒤로 계속 이동해야 할 수 있어서...

- 3원칙: 교환된 것이 없다면 모든것이 정렬완료된 상태이므로 loop를 종료한다.


0부터 n까지 계속 비교하기 때문에 

Best case: O() : 정렬이 거의 다 되어있는 상태에서...

Worst case: O() : 역순정렬된 상태 일때...


이미 정렬된 상태라고 예상될때 쓰는게 좋지 않을까 함


public class BubbleSort {


    public void sort(Comparable[] array) {

        boolean isCompleted = true;

        while (isCompleted) {

            isCompleted = false;

            for (int i = 0; i + 1 < array.length; i++) {

                if (array[i].compareTo(array[i + 1]) > 0) {

                    Comparable temp = array[i];

                    array[i] = array[i + 1];

                    array[i + 1] = temp;

                    isCompleted = true;

                }

            }

        }

    }

}



Reference:

https://en.wikipedia.org/wiki/Bubble_sort

'Algorithms > Sorting' 카테고리의 다른 글

Quick sort(퀵 정렬)  (0) 2017.06.24
Merge sort(병합 정렬)  (0) 2017.02.08
Selection sort(선택 정렬)  (0) 2017.02.08
Insertion sort(삽입 정렬)  (0) 2017.02.06
Bubble sort(거품? 정렬)  (0) 2017.02.06

+ Recent posts