Quicksort 하나로 얼마나 짧게 쓸 수 있는지.

솔직히 말하면, 나는 한 번도 빠른 정렬을 쓸 수 없었고, 항상 각양각색의 오류가 있었다.
빨리 줄을 서는 것은 번거롭기 때문에 그것을 조정할 방법이 없다. 왜냐하면 그것은
반복적으로 생성되는 것은 정적 디버깅을 하거나 끊임없이 출력된 그룹의 상태를 통해 오류의 가능성을 추측할 수 있습니다.그러나 빠른 배열의 기본 사상은 매우 간단하다.
하나의 수조를 받아서 하나의 수를 고른 다음에 그것보다 작은 노점 수를 왼쪽에 놓고, 그것보다 큰 노점 수를 오른쪽에 놓고, 이 수조와 좌우 두 노점 수를 귀속시키는 빠른 배열 과정을 실행한다.

다음은 가장 자주 사용하는 C 언어로 빠른 정렬을 작성합니다.

먼저 위조 코드를 작성할 수 있습니다.

void quicksort(int array[], int left, int right)

{

    //Do nothing if left <= right

    //p <- Get a number from array

    //Put elements <= p to the left side

    //Put elements >= p to the right side

    //Put p in the middle slot which index is pivot

    //Recursive quicksort the left parts and right parts

}

그리고 천천히 이 위조 코드를 C 코드로 바꾸세요.

Step 1:

void quicksort(int array[], int left, int right)

{

    if(left<right)

    {

        //p <- Get a number from array

        //Put elements <= p to the left side

        //Put elements >= p to the right side

        //Put p in the middle slot which index is pivot

        //Recursive quicksort the left parts and right parts

    }

}

Step 2: 수조의 어떤 원소를 얻을 수 있습니다. 여기서 항상 맨 왼쪽의 원소를 얻을 수 있습니다.

void quicksort(int array[], int left, int right)

{

    if(left<right)

    {

        int p=array[left];

        //Put elements <= p to the left side

        //Put elements >= p to the right side

        //Put p in the middle slot which index is pivot

        //Recursive quicksort the left parts and right parts

    }

}

Step 3: 이것은 비교적 번거로운 단계입니다. 그룹을 훑어볼 수 있습니다. 표기값보다 작은 수를 만나면 앞의 숫자와 교환합니다. 이렇게 한 번 훑어본 후에 작은 숫자가 앞쪽으로 옮겨집니다.

void quicksort(int array[], int left, int right)

{

    //Do nothing if left <= right

    if(left<right)

    {

        //p <- Get a number from array

        int p=array[left];

        //Put elements < p to the left side

        //Put elements >= p to the right side

        int i=left,j;

        for(j=left+1;j<=right;j++)

        {

            if(array[j]<p)

            {

                i++;

                swap(array,i,j);

            }

        }

        //Put p in the middle slot which index is pivot

        swap(array,i,left);

        //Recursive quicksort the left parts and right parts

    }

}

Step4: 이전에 한 절차가 수조를 나누는 과정이라는 것을 쉽게 발견할 수 있으며 이해하기 쉽도록 함수로 끌어올릴 수 있다.이와 동시에 빠른 속도로 좌우 두 부분을 배열하면 된다.

void partition(int array[],int left, int right)

{

    //p <- Get a number from array

    int p=array[left];

    //Put elements < p to the left side

    //Put elements >= p to the right side

    int i=left,j;

    for(j=left+1;j<=right;j++)

    {

        if(array[j]<p)

        {

            i++;

            swap(array,i,j);

        }

    }

    //Put p in the middle slot which index is pivot

    swap(array,i,left);

    return i;

}

void quicksort(int array[], int left, int right)

{

    //Do nothing if left <= right

    if(left<right)

    {

        int pivot=partition(array,left,right);

        //Recursive quicksort the left parts and right parts

        quicksort(array,left,pivot-1);

        quicksort(array,pivot+1,right);

    }

}

Step 5: 마지막 래퍼를 사용하면 기본적인 qsort를 완성할 수 있습니다

void q_sort(int array[], int size)

{

    quicksort(array, 0, size-1);

}

물론 위의 절차는 많은 테스트와 디버깅 과정을 줄였다. 전에 나도 말했듯이 나는 단번에 정확한 빠른 줄을 쓸 수 없지만 한 걸음 한 걸음 오면 쓸 수 있다.다음은 제목: Quicksort는 얼마나 짧게 쓸 수 있습니까?이전의 C 프로그램으로 말하자면 그것을 짧게 하는 경로는 함수를 전개하고 괄호를 제거하는 등 짝퉁 방법일 뿐이다.

Step 1: 파티션 함수를 확장하고 메모를 제거합니다.

void quicksort(int array[], int left, int right)

{

    if(left<right)

    {

        int p=array[left];

        int pivot=left,j;

        for(j=left+1;j<=right;j++)

        {

            if(array[j]<p)

            {

                pivot++;

                swap(array,pivot,j);

            }

        }

        swap(array,pivot,left);

        quicksort(array,left,pivot-1);

        quicksort(array,pivot+1,right);

    }

}

Step 2: 임시 변수, 대괄호를 제거하고 자증자감 동작을 한 문장에 넣습니다

void quicksort(int array[], int left, int right)

{

    if(left<right){

        int pivot=left,j;

        for(j=left+1;j<=right;j++)

            if(array[j]<array[left])

                swap(array,++pivot,j);

        swap(array,pivot,left);

        quicksort(array,left,pivot-1);

        quicksort(array,pivot+1,right);

    }

}

Step 3: C 포인터 산수를 사용하여 추가 매개변수 제거

void quicksort(int *array, int n)

{

    if(n>1){

        int pivot=0,j;

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

            if(array[j]<array[0])

                swap(array,++pivot,j);

        swap(array,0,pivot);

        quicksort(array,pivot);

        quicksort(array+pivot+1,n-pivot-1);

    }

}

그러면 원래 20여 줄이던 빠른 줄을 10줄로 줄일 수 있지만 이게 무슨 의미가 있겠는가. 프로그램의 가독성이 크게 떨어지고 운행 효율도 조금도 향상되지 않았다.이 밖에 지침산술은 각종 경계를 넘는 오류를 초래할 가능성이 높다.게다가 C 언어의 경우 아무리 짧아도 얼마 남지 않는다. 다음은 다른 언어에서 빨리 이루어지는 것을 볼 수 있다. 자바, C# 같은 언어는 실제적으로 C와 같은 계열이다(모두 Von-Neuman 체계를 바탕으로 하는 Imperative Language).Declarative Language에서 Quicksort를 작성하는 방법을 보여 드리겠습니다. 여기서 Scheme (함수식 언어) 와Python (스크립트 언어) 을 사용해서 보여 드리겠습니다.

이제 Scheme로 만든 Quicksort를 보여드릴게요.

Scheme는 MIT의 Guy Steele과 Jay Sussman이 개발한 함수식 프로그래밍 언어로 유명한 Sicp(
Structure and Intepretation of Computer Programs) 및 Htdp(
How to design programs)는 바로 Scheme 언어를 사용하는데 그의 문법은 매우 간단하지만 기능이 매우 강하다.mit의 6.001 과정은 scheme를 컴퓨터 전공 학생의 입문 언어로 선택한다.

;; define x as value 1

(define x 1)

;; define l as a list of 1 2 3

(define x (list 1 2 3))

;; define f as a square function

(define (f x) (* x x))

;; define a function use lambda

(define f (lambda (x) (* x x)))

;; use a high-order function filter, will return (list 1 2 3)

(filter (lambda (x) (<= x 3)) (list 1 2 3 4 5))

Scheme 언어에 대한 자세한 내용은
The little schemer나 인터넷의specification은 여기서 설명할 필요가 없습니다.

빠른 순서로 돌아가서 이전의 사고방식에 따라 위코드를 먼저 쓰자.

;; Sort a number list via quicksort algorithm

;; list of numbers -> list of numbers

(define (q-sort l)

  ;;get a number p from l

  ;;get numbers<=p from l-{p} as small part

  ;;get number>p from l-{p} as bigger part

  ;;recursively quicksort on small part and bigger part

  ;;combine small part, p, bigger part together as the sorted list

  )

Step 1: 먼저 시퀀스의 어떤 수를 얻고, 여기서 첫 번째 수를 얻습니다.

;; Sort a number list via quicksort algorithm

;; list of numbers -> list of numbers

(define (q-sort l)

  ;;get a number p from l

  (let ((p (first l)))

      ;;get numbers<=p from l-{p} as small part

      ;;get number>p from l-{p} as bigger part

      ;;recursively quicksort on small part and bigger part

      ;;combine small part, p, bigger part together as the sorted list

     )

  )

Step 2: 표식 값보다 작은 노점 수와 큰 노점 수를 시퀀스에서 추출하여 귀속된 빠른 배열 호출

;; Sort a number list via quicksort algorithm

;; list of numbers -> list of numbers

(define (q-sort l)

  (cond

    [(empty? l) empty]

    [(empty? (rest l)) (list (first l))]

    [else

    ;;get a number p from l

    ;;get numbers<=p from l-{p} as small part

    ;;get number>p from l-{p} as bigger part

     (let ((small-part (filter (lambda (x) (<= x (first l))) (rest l)))

           (big-part (filter (lambda (x) (> x (first l))) (rest l))))

        ;;recursively quicksort on small part and bigger part

       )]

    )

  )

Step 3: 이 귀속 함수에 종료 조건을 추가합니다.

;; Sort a number list via quicksort algorithm

;; list of numbers -> list of numbers

(define (q-sort l)

  (cond

    [(empty? l) empty]

    [(empty? (rest l)) (list (first l))]

    [else

    ;;get a number p from l

    ;;get numbers<=p from l-{p} as small part

    ;;get number>p from l-{p} as bigger part

     (let ((small-part (filter (lambda (x) (<= x (first l))) (rest l)))

           (big-part (filter (lambda (x) (> x (first l))) (rest l))))

        ;;recursively quicksort on small part and bigger part

       (append (q-sort small-part)

               (list (first l))

               (q-sort big-part)))]

    )

  )

scheme 프로그램의 큰 특징은 성명성이라는 것을 발견할 수 있다. 너는 그것에게만 알려주면 된다
what to do, C 프로그램의 경우 강조
How to do, 실제로 위의 프로그램은 주석을 필요로 하지 않습니다. 자신의 코드는 이미 자신의 용도를 설명하기에 충분합니다.

최종 Scheme 프로그램:

;; Sort a number list via quicksort algorithm

;; list of numbers -> list of numbers

(define (q-sort l)

  (cond

    [(empty? l) empty]

    [(empty? (rest l)) (list (first l))]

    [else

     (let ((small-part (filter (lambda (x) (<= x (first l))) (rest l)))

           (big-part (filter (lambda (x) (> x (first l))) (rest l))))

       (append (q-sort small-part)(list (first l))(q-sort big-part)))]

    )

  )

마지막으로 파이썬으로 빠른 정렬을 만드는 방법을 살펴보겠습니다.

주의해야 할 것은 Python은 앞의 C, Scheme 언어와 다르다.
multi-paradigmprogramminglanguage, 다시 말하면python으로proceduralprogramming도 할 수 있고oop심지어fp도 할 수 있다.우선 C의 사상으로python 버전의 빠른 줄을 쓴다.

Step 1: 위조 코드를 나열하고 실행하려면

def q_sort(l):

    #get first number p from l

    #move elements<p to the left side

    #move elements>=p to the right side

    #recursively quicksort left and right part

    #combine them together

Step 2: 함수 내부에 정의된 함수의 성질을 지원하는 Python 지원

def q_sort(l):

    def quicksort(l,left,right):

        #get first number p from left end

        #move elements<p to the left side

        #move elements>=p to the right side

        #recursively quicksort left and right part

        #combine them together

    quicksort(l,0,len(l)-1)

Step 3: list 요소를 이동하는 과정을 한 걸음 더 세분화하면 이 함수를 완성할 수 있습니다.Python은 다중 값을 지원하기 때문에 원소를 교환하는 데 매우 편리합니다

def q_sort(l):

    def quicksort(l,left,right):

        if right>left:

            #get first number p from left end

            pivot,j,tmp=left,left+1,l[left]

            #move elements<p to the left side

            #move elements>=p to the right side

            while j<=right:

                if l[j]<tmp:

                    pivot=pivot+1

                    l[pivot],l[j]=l[j],l[pivot]

                j=j+1

            l[left],l[pivot]=l[pivot],l[left]

            #recursively quicksort left and right part

            quicksort(l,left,pivot-1)

            quicksort(l,pivot+1,right)

    quicksort(l,0,len(l)-1)

python의 좋은 특징은 바로
list comprehension, 이 기능을 이용하여 성명성이 강한 코드를 쓸 수 있습니다. 예를 들어 다음과 같습니다.

# Get all even numbers between 1 and 100

[x for x in range(1,101) if x%2==1]

# Get all line which start with 'From'

[line for line in lines if line.startwith('From')]

우리는 이 기능을 직접 사용하여 더욱 알기 쉬운 Quicksort를 구축하여 이전의 첫 단계로 돌아갈 수 있다.

def q_sort(l):

    #get first number p from l

    #move elements<p to the left side

    #move elements>=p to the right side

    #recursively quicksort left and right part

    #combine them together

Step2:python의list slice와list comprehension을 이용하여 표기치보다 크고 작은 두 부분을 쉽게 얻을 수 있고 그것들을 연결하면 된다

def q_sort(l):

    #get first number p from l

    p=l[0]

    #move elements<p in l-{p} to the left side

    small_part=[x for x in l[1:] if x<p]

    #move elements>=p in l-{p} to the right side

    big_part=[x for x in l[1:] if x>=p]

    #recursively quicksort left and right part and combine them together

    return q_sort(small_part)+[p]+q_sort(big_part)

실행 프로그램,oops, 사순환에 들어갔습니다.

Step 3: 종료 조건 추가

def q_sort(l):

    if len(l)<=1:

        return l

    else:

        #get first number p from l

        p=l[0]

        #move elements<p in l-{p} to the left side

        small_part=[x for x in l[1:] if x<p]

        #move elements>=p in l-{p} to the right side

        big_part=[x for x in l[1:] if x>=p]

        #recursively quicksort left and right part and combine them together

        return q_sort(small_part)+[p]+q_sort(big_part)

이번 운행 결과는 정상입니다. 주의해야 할 것은,
이거q_sort는 제자리 정렬을 하는 것이 아니라 끊임없이 새로운list를 생성합니다.list의 요소가 많을 때 성능에 큰 부정적인 영향을 미칠 수 있습니다. 여기는python의 특성을 보여주기 위해 이렇게 썼습니다.어떻게 그것을 더욱 짧게 만듭니까?일단 주석을 빼보도록 하겠습니다.

Step 4: 주석 제거

def q_sort(l):

    if len(l)<=1:

        return l

    else:

        p=l[0]

        small_part=[x for x in l[1:] if x<p]

        big_part=[x for x in l[1:] if x>=p]

        return q_sort(small_part)+[p]+q_sort(big_part)

주석 제거 후 q_sort 함수는 8줄만 남았는데 더 짧을 수 있습니까?답은 긍정적이다.주의q_sort에 임시 변수를 많이 썼어요. 제거할 수 있어요.

Step 5: 임시 변수 제거

.45, 6, 7, 913. 5줄밖에 안 남았어요!

Step 6: Python의 3원 표현식ifelse를 이용하여 위의 함수를 개작합니다. 이곳의 논리는 동일합니다.

def q_sort(l):

    if len(l)<=1:

        return l

    else:

        return q_sort([x for x in l[1:] if x<l[0]])+[l[0]]+q_sort([x for x in l[1:] if x>=l[0]])

이제 두 줄만 남았습니다. 주의해야 할 것은python도lambda표현식을 제공했기 때문에q_sort는 더욱 간소화될 수 있습니다.

Final Step: lambda 표현식을 사용하여 다시 단순화

.Quicksort 하나로 얼마나 짧게 쓸 수 있을까요?위의 코드가 답을 주었으니 한 줄이면 충분하다.

요약:

우리는 서로 다른 언어가 같은 문제를 처리할 때 채택하는 방안도 판이하게 다르다는 것을 볼 수 있다.
C 언어는 how to do를 강조하고 Scheme, Python은 what to do를 강조한다.C를 사용하면 디테일을 중시해야 한다. 모든 작은 실수가 프로그램을 다운시킬 수 있기 때문이다. 이것은 imperative language의 통성이다. 예를 들어 scheme,python 같은 언어는 실현된 디테일이 아니라 문제를 해결하는 논리를 중시한다. 우리는 컴퓨터에게 what to do만 알려주고 컴파일러는 당신에게 대응하는 코드를 생성할 것이다.이렇게 하면 우리는 디버깅 프로그램의 세부 사항에 많은 정력을 들일 필요가 없다.
일부 사람들은 프로그램 언어는 사상을 표현하는 한 방식일 뿐이라고 생각한다. 다시 말하면 언어는 중요하지 않고 중요한 것은 이른바 사상이라고 생각한다.심지어 어떤 사람들은 언어가 모두 통하기 때문에 주류 언어 (예를 들어 C/C++/Java/C# 등) 를 파악하면 충분하다고 생각한다.확실히 C언어의 숙련자는 자바 문법을 배우는데 2, 3일의 시간이 될 수 있지만 C++의 숙련자는 C#를 사용하면 오전 내내 사용하지 못한다.그러나 주의해야 할 것은 한 언어의 문법을 아는 것과 한 언어를 능숙하게 사용하는 것은 매우 다르다. 모든 언어는 독특한 면이 있는데 이런 성분은 이 언어를 사용하는 데 상당한 시간이 걸려야 체득할 수 있다.
Steve McConnel은 Program on a language[4]가 아니라 Program into a language를 원한다고 말한 적이 있다. 예를 들어 내가 C에 익숙하다고 가정하고 이틀 동안 자바의 문법을 배웠다고 가정했다. 그러나 이것은 내가 제대로 된 자바 프로그램을 쓸 수 있는 것은 아니다. 왜냐하면 나는 GC, 스프링, Hibernate 등 일련의 프레임워크도 모르고 OOP도 익숙하지 않기 때문이다.다시 말하면 우리는 중학교 때부터 영어를 배웠고 지금도 10년이 넘었지만 우리가 말하는 영어는 여전히 외국인에게 칭리쉬라고 불린다. why?나는 이것이 우리가 발음이 좋지 않거나 유창하지 않은 것이 아니라
우리는 줄곧 thinking in the Chinese way였는데, 이런 상황에서 순수한 영어를 말할 수 없었다.
그래서 저는 언어무관론과 같은 관점은 모두 잘못된 것이라고 생각합니다. 한편, 이런 관점을 가진 사람들의 안목은 좁고 명령식 프로그래밍 언어의 범위에 한정되어 있습니다(다른 모범적인 프로그래밍 언어의 존재를 전혀 모르기 때문에 그들은 모든 언어가 서로 통한다고 생각합니다).한편, 이러한 관점을 가진 사람들은 언어가 사상에 영향을 주지 않는다고 생각하지만 실제로는 그렇지 않다. Lisp프로그래머와 C프로그래머가 같은 문제를 처리하는 사고방식은 분명히 차이가 크다. 프로그래밍 언어를 버리고 서로 다른 언어, 예를 들어 중국어와 영어를 해도 사람의 사고방식에 영향을 미친다(유명한 Sapir-Whorf 가설).이것이 바로 우리가 흔히 말하는 동양인 사유와 서양인 사유의 발생 원인 중의 하나이다[5].
Eric Raymond는 Hacker로서 Python, C/C++, Java, Perl 등 5개 언어를 익혀야 한다고 그의 How to become a hacker에서 언급한 바 있다.[6] 왜냐하면 그들은 각각 다른 프로그래밍 방식을 대표하기 때문이다.
It's best, actually, to learn all five of Python, C/C++, Java, Perl, and LISP. Besides being the most important hacking languages, they represent very different approaches to programming, and each will educate you in valuable ways.
Peter Norvig는 보다 직접적입니다[7]:
Learn at least a half dozen programming languages. Include one language that supports class abstractions (like Java or C++), one that supports functional abstraction (like Lisp or ML), one that supports syntactic abstraction (like Lisp), one that supports declarative specifications (like Prolog or C++ templates), one that supports coroutines (like Icon or Scheme), and one that supports parallelism (like Sisal)
그래서 얘기하는 거예요.
Teach Yourself Programming in Ten Years

References

[1] The practice of Programming. Brian W Kernighan and Rob Pike. Addison Wisley [2] How to design programs. MIT Press. [3] Learning Python 3rd edition. O'Reilly Press [4] Code complete 2nd edition. Microsoft Press [5] Linguistic Relativity. Wikipedia [6] How to become a hacker. Eric S Raymond [7] Learning programming in Ten Years. Peter Norvig