Quick Sort

위키백과 사전에 나온게 가장 심플하고 이해하기 쉽다.

Quick Sort 는 A.R 호어 가 개발한 정렬 알고리즘이다.
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
Quick Sort 는 n 개의 데이터를 정렬할 때, 최악의 경우 O(n2)번의 비교를 수행하고,
평균적으로 O(n log n) 번의 비교를 수행한다.

Quick Sort 의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계 되어 있고
(그 이유는 메모리 참조가 지역화 되어 있기 때문에 CPU, 캐시의 히트 율이 높아지기 때문이다...뭔소리래..) ,
대부분의 실질적인 데이터를 정렬할 때
제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다.

때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다.
그리고 Quick Sort는 정렬을 위해 O(log g)만큼의 memory를 필요로 한다.
또한 Quick Sort 는 불안정 정렬에 속한다.

분할 작업을 순환적으로 반복하면서 기준 값(Pivot)의 왼쪽 부분 집합과 오른쪽 부분 집합을 정렬하는 방법

1.리스트 가운데 하나의 원소를 선택한다. 이렇게 고른 것이 Pivot 이다.

2.Pivot 앞에는 Pivot 보다 작은 모든 원소들이 오고, Pivot 뒤에는 Pivot 보다 값이 큰 모든 원소들이 

   오도록 Pivot을 기준으로 리스트를 둘로 나눈다.

  이렇게 리스트를 둘로 나눈 것을 분할 이라고 하고, 분할을 마친 뒤에 Pivot은 더 이상 움직이지 않는다.

3. 분할된 두개 의 작은 리스트에 대해 재귀적으로 이 과적을 반복한다. 

    재귀는 리스트의 크기가 0 이나 1이 될 때 까지 반복된다.

예제

1. Pivot 은 p , 리스트의 왼쪽과 오른 쪽 끝에서 시작한 인덱스를 i , j 라고 하자

2. 리스트 왼쪽에 있는 i의 위치의 Pivot 값보다 크고, 오른쪽에 있는 j 위치의 값은
Pivot 보다 작으므로 둘을 교환 한다.

3. j 위치의 값이 Pivot 값보다 작지만, i 의 위치의 값도 피벗보다 작으므로
 교환하지 않는다.

4. I 위치를 피벗 값보다 큰 값이 나올 때 까지 진행해 j 위치의 값과 교환한다.

5. I 위치와 j 위치의 값이 만나면 , j 위치의 값과 Pivot 값을 교환한다.

6. Pivot 값 좌우의 리스트에 대해 퀵 정렬을 재귀적으로 수행한다.

그럼 이렇게 해서 끝!

자!!! 이제 Java Programming 시간... 

http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html

여기에 있는 걸 가지고 공부를 해봤다.

두가지 였다.. 재귀 함수 호출 과 JUnit 테스트!!!

public class Quicksort {

    

    private int[] numbers; //정렬하고자 하는 배열

    private int number; //배열의 길이 

    

    public void sort(int[] values){

    //check for empty or null array

    if( values == null || values.length == 0){

    return;

    }

    this.numbers = values;

    number = values.length;

    //퀵정렬 해보랍니다. low 는 0 그리고, high 는 배열 길이 (다시 말해 배열의 위치)

    quicksort(0,number -1);

    }

public void quicksort(int low, int high){

int i = low, j = high;

//Get the pivot element from the middle of the list.

int pivot = numbers[low + (high - low)/2];

//Divide into two lists

while(i < j){

// If the current value from the left list is smaller than the pivot  element

// then get the next element from the left list

//피봇보다 작으면 그냥 패스 

while(numbers[i] < pivot){

i++;

}

//If the current value from the right list is larger than the pivot element

// then get the next element from the right list.

//피봇보다 크면 다음으로 패스 

while(numbers[j] > pivot){

j--;

}

//If we have found a values in the left list which is larger than the pivot element 

// and if we have found a value in the right list which is smaller than the pivot  element

// then we exchange the value.

// As we are done we can increase i and j

if( i <= j){

exchange(i,j);

i++;

j--;

}

//recursion

if(low < j)

quicksort(low, j);

if(i < high)

quicksort(i,high);

}

}

private void exchange(int i , int j){

int temp = numbers[i];

numbers[i] = numbers[j];

numbers[j] = temp;

}

    

}

package com.neonex.npa.service;

import static org.junit.Assert.assertTrue;

import static org.junit.Assert.fail;

import java.util.Arrays;

import org.junit.Before;

import org.junit.Test;

import scala.util.Random;

import com.neonex.npa.controller.Quicksort;

public class QuicksortTest {

private int[] numbers;

private final static int SIZE = 7;

private final static int MAX = 20;

@Before

public void setup() throws Exception{

numbers = new int[SIZE];

Random generator = new Random();

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

numbers[i] = generator.nextInt(MAX);

}

}

@Test

public void testNull(){

Quicksort sorter = new Quicksort();

sorter.sort(null);

}

@Test

public void testEmpty(){

Quicksort sorter = new Quicksort();

sorter.sort(new int[0]);

}

@Test

public void testSimpleElement(){

Quicksort sorter = new Quicksort();

int[] test = new int[1];

test[0] = 5;

sorter.sort(test);

}

@Test

public void testSpecial(){

Quicksort sorter = new Quicksort();

int[] test ={ 5, 5, 6, 6, 4, 4, 5, 5, 4, 4, 6, 6, 5, 5 };

sorter.sort(test);

if(!validate(test)){

fail("Should not happen");

}

printResult(test);

}

@Test

public void testQuicksort(){

for(Integer i : numbers){

System.out.print(i + " ");

}

long startTime = System.currentTimeMillis();

Quicksort sorter = new Quicksort();

sorter.sort(numbers);

long stopTime = System.currentTimeMillis();

long elapsedTime = stopTime - startTime;

System.out.println("Quicksort : " + elapsedTime);

if(!validate(numbers)){

fail("Should not happen");

}

assertTrue(true);

}

@Test

public void testStandardSort(){

long startTime = System.currentTimeMillis();

   Arrays.sort(numbers);

   long stopTime = System.currentTimeMillis();

   long elapsedTime = stopTime - startTime;

   System.out.println("Standard Java sort " + elapsedTime);

   if (!validate(numbers)) {

       fail("Should not happen");

     }

     assertTrue(true);

}

private boolean validate(int[] numbers){

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

if(numbers[i] > numbers[i +1]){

return false;

}

}

return true;

}

private void printResult(int[] numbers){

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

System.out.print(numbers[i]);

}

System.out.println();

}

}

** 추가로 오래 간만에 log 에 대해서 .... (log = logarithm)

How many of one number do we multiply to get another number?

Example : How many 2s do we multiply to get 8?

Answer  :  2x2x2 = 8 , so we needed to multiply 3 of the 2s to get 8.

So the logarithm is 3.

What is log5(625) …?
We are asking “how many 5s need to be multiplied together to get 625?

5x5x5x5 = 625 , so we need 4 of the 5s.
Answer : log5(625) = 4

A가 1이 아닌 양수 일 때 (A != 1 , A > 0)  , x 와 y 사이에  x = Ay 라는 관계가 있으면, y는 A를 밑으로 하는 x의 로그라 하고 logAX 라고 나타 냅니다. 이 때 X를 Y의 진수라고 합니다.
또 y = logaX를 x,y 사이의 함수관계로 볼 때 y를 x의 로그 함수라고 합니다.

기본적인 성질은

a > 0 , a != 1 이고 , x > 0 , y > 0  일때

(1)logaa = 1 , loga1 = 0

(2)logaxy = logax + logay

(3)logaX/Y = logaX = logaY