본문 바로가기

정렬

(4)
Collections.sort 을 이용한 객체 정렬 ABC.java Test.java - Output - list를 정렬하는 방법을 찾다가 찾은 방법입니다. CompareTo Method를 이용해서 두 객체의 비교가 일어납니다. modified mergesort 가 이용되고 stable이 유지되며 O(n^2) 은 피하며 nlog(n)이 보장된다고 합니다.
퀵정렬(quick sort) 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 이와 같은 순서로 놓이게 된다. 그럼 p..
병합정렬 (Merge Sort) 테스트 파일은 삽입정렬과 같지만 인스턴스생성해주는 부분만 바뀌었습니다. 두 조각으로 계속 나누다가 마지막에 하나가 남으면 다시 위로 병합하면서 정렬하는 병합정렬 이번에는 삽입정렬과는 다르게 생성자를 따로 만들지 않았다. 정렬할때 매개변수로 바로 입력값을 넣게 하였다. 실제로 사용자가 쓸수 있는 메소드는 단 하나 sort 메소드 테스트는 수업시간에 나온 예제 숫자입니다. 삽입정렬과 같은 숫자네;; 9 1 3 2 7 5 4 8
삽입정렬 (Insertion Sort) 오늘 배운 삽입정렬이다. InsertionSort.class 가 삽입정렬 클래스 입니다. sort_test.class 는 정렬 테스트를 위한 메인함수가 있는 클래스 입니다. 다른 정렬도 배우는 대로 추가할까 합니다. 멤버변수 data는 배열인데... 오타네요;; int data[] 이게 맞아요; 생성자와 정렬메소드를 제외하고는 외부에서 쓸필요가 없으므로 private로 접근제한 하였습니다. 생성자 함수로 정렬할 배열값을 입력하고 sort() 메소드를 호출하므로써 모든 과정이 끝납니다. sort() 는 정렬된 배열을 리턴합니다. 수업시간에 예제로 나온 숫자들로 테스트 하였습니다. 다른 숫자는 테스트안해봐서... 정확성을 뭐라 말할 수가 없네요;; 9 1 3 2 7 5 4 8