Charles Antony Richard Hoare & Quick Sort

Charles Antony Richard Hoare ,영국 컴퓨터 과학자 입니다. 우리가 많이 들 알고 있는 정렬 알고리즘으로 사용되는 QuickSort 의 개발을 하신 분이죠. 

진정한 테스트는 코드에서 버그들을 감지하는 것이 아니고, 코드를 설계하고 생산한 사람들의 방법들, 집중력, 그리고 기술들에서 부족한 부분들을 감지하는 것이다. 

The real value of tests is not that they detect bugs in the code, but that they detect inadequacies in the methods, concentration, and skills of those who design and produce the code.

The Emperor's Old Clothes 

http://zoo.cs.yale.edu/classes/cs422/2011/bib/hoare81emperor.pdf

There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies and the other way is to make it so complicated that there are no obvious deficiencies.

소프트웨어를 설계하는 데는 두 가지 방법이 있다. 하나는 단순하게 만들어서 아무 결함이 없도록 만드는 것이고, 다른 하나는 복잡하게 만들어서 눈에 드러나는 결함이 없도록 만드는 것이다.” 단순함. 군더더기가 없는 것. 그게 핵심이다. 

There is nothing a mere scientist can say that will stand against the flood of a hundred million dollars. But there is one quality that cannot be purchased in this way — and that is reliability. The price of reliability is the pursuit of the utmost simplicity. It is a price which the very rich find most hard to pay.

쉽지만은 않지만, 항상 테스트에 대한 중요성과 더불어,

단순함을 유지하는 개발을 위해 노력해야 하겠다.

참고로  Quick Sort는 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.

1) 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 

2) 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

3) 분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

public void quickSort(int left, int right)

{

   int i,j;

   TableEntry p, tmp

   if(left<right)

   {

      i=left;

      j=right;

      p=table[left];

      //분할 과정

      while(i<j)

      {

         while(table[j].key>p.key)         j--;

         while(i<j && table[i].key<=p.key) i++;

         tmp = table[i];

         table[i]=table[j];

         table[j]=tmp;

      }

      table[left] = table[i];

      table[i]=p;

      //정렬 과정

      quickSort(left,i-1);

      quickSort(i+1,right);   

   }

}

정리를 할 때마다 새롭게 느껴지면 큰일인데 ㅎㅎㅎ