'퀵소드'에 해당되는 글 1건

  1. 2009.03.19 퀵정렬(quick sort)
Programming2009.03.19 18:42

QuickSort 의 시작은 임의의 수를 pivot 이라고 정하면서 시작된다.

int data[] = {6, 9, 14, 4, 7, 3, 1, 10};

이런 값들의 List 가 있을경우 6을 pivot을 정한다고 가정하면 j가 [1]~[7] 으로 움직인다고 하자

그리고 i=0 으로 초기화 되어있다. 그럼 j는 1부터 커지면서 pivot 인  6보다 작은 수가 있는지 찾는다.

만약 작은 수가 있는 j를 발견하면 ++i 와 j를 바꾼다. data[++i] 와 data[j] 를 바꾸는 것이다.

그럼 처음으로 바뀌는 번호가 4와 9가 된다. j는 3 이고 i는 ++i가 되어서 1인 경우이다.

이렇게 반복해서 [7]까지 가면 pivot, pivot >  x, pivot < x 이와 같은 순서로 놓이게 된다.

그럼 pivot 위치를 중간에 높이게 하면된다. 이때 쉽게 바꾸는 방법은 위에서 사용한 i를 쓰면 마지막으로

작은 수를 옮긴 위치를 알수 있기때문에 한번에 바꿀수가 있다

QuickSort를 c언어로 작성하여 첨부파일에 포함하였다.
신고
Posted by 초프(초보 프로그래머)