'정렬'에 해당되는 글 4건

  1. 2009.10.13 Collections.sort 을 이용한 객체 정렬
  2. 2009.03.19 퀵정렬(quick sort)
  3. 2009.03.12 병합정렬 (Merge Sort)
  4. 2009.03.12 삽입정렬 (Insertion Sort)
Programming/JAVA2009.10.13 00:34

ABC.java


Test.java


- Output -


list를 정렬하는 방법을 찾다가 찾은 방법입니다. CompareTo Method를 이용해서 두 객체의 비교가 일어납니다.

modified mergesort 가 이용되고 stable이 유지되며 O(n^2) 은 피하며 nlog(n)이 보장된다고 합니다.
신고
Posted by 초프(초보 프로그래머)
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 초프(초보 프로그래머)
Programming2009.03.12 20:10


테스트 파일은 삽입정렬과 같지만 인스턴스생성해주는 부분만 바뀌었습니다.

두 조각으로 계속 나누다가 마지막에 하나가 남으면 다시 위로 병합하면서 정렬하는 병합정렬

이번에는 삽입정렬과는 다르게 생성자를 따로 만들지 않았다.
정렬할때 매개변수로 바로 입력값을 넣게 하였다.
실제로 사용자가 쓸수 있는 메소드는 단 하나 sort 메소드



테스트는 수업시간에 나온 예제 숫자입니다. 삽입정렬과 같은 숫자네;;

9 1 3 2 7 5 4 8  <-- 입력값
1 2 3 4 5 7 8 9  <-- 정렬후

신고
Posted by 초프(초보 프로그래머)
Programming2009.03.12 19:35

 


오늘 배운 삽입정렬이다.

InsertionSort.class 가 삽입정렬 클래스 입니다.
sort_test.class 는 정렬 테스트를 위한 메인함수가 있는 클래스 입니다.

다른 정렬도 배우는 대로 추가할까 합니다.

멤버변수 data는 배열인데... 오타네요;; int data[] 이게 맞아요;

생성자와 정렬메소드를 제외하고는 외부에서 쓸필요가 없으므로 private로 접근제한 하였습니다.
생성자 함수로 정렬할 배열값을 입력하고 sort() 메소드를 호출하므로써 모든 과정이 끝납니다. sort() 는 정렬된 배열을 리턴합니다.


수업시간에 예제로 나온 숫자들로 테스트 하였습니다. 다른 숫자는 테스트안해봐서... 정확성을 뭐라 말할 수가 없네요;;

9 1 3 2 7 5 4 8  <--- 입력값 
1 2 3 4 5 7 8 9  <--- 정렬후

신고
Posted by 초프(초보 프로그래머)