정렬(버블정렬, 삽입정렬, 퀵정렬, 병합정렬)

JUnit

@Test 어노테이션을 통해서 단위테스트 진행 (이클립스에 있는 JUnit 라이브러리 이용. JUnit은 자바용 단위 테스트 툴.)

경로 : 프로젝트 > properties > Libraries > Add Library > JUnit

Run as > JUnit Test 로 테스트 결과 조회.

 

import static org.junit.Assert.*;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

//유닛테스트 활용
public class Test1 {
	
	//1. int형 배열 정렬
	@Test
	public void sortInts(){
		final int[] numbers = {-3,-5,1,7,4,-2};
		final int[] expected1 = {-5,-3,-2,1,4,7};
		
		Arrays.sort(numbers);
		assertArrayEquals(expected1,numbers);
	}

	//2. String형 배열 정렬
	@Test
	public void sortObjects(){
		final String[] strings = {"z", "x", "y", "abc", "zzz", "zazzy"};
		final String[] expected2 = {"abc", "x", "y", "z", "zazzy", "zzz"};
		
		Arrays.sort(strings);
		assertArrayEquals(expected2,strings);
	}	
    
    //3. Comparable 인터페이스 사용하지 않고 정렬하기
    @Test
    public void sortNotComparable() {
        final List<NotComparable> objects = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            objects.add(new NotComparable(i));
        }

        try {
            Arrays.sort(objects.toArray());
        } catch (Exception e) { 
            return;
        }

        fail();
    }
	
	//3-1. 이너클래스 생성
    private static class NotComparable {
        private int i;
        private NotComparable(final int i) {//생성자로 변수 초기화
            this.i = i;
        }
    }
	
	//4. 사용자가 지정한 순서로 정렬하기
	@Test
	public void customSort(){
		final List<Integer> numbers = Arrays.asList(4,7,1,6,3,5,4);
		final List<Integer> expected3 = Arrays.asList(7,6,5,4,4,3,1);
		
		Collections.sort(numbers,new ReverseNumericalOrder());
		assertEquals(expected3,numbers);
	}	
	
}
//4-1. 사용자가 지정한 순서로 정렬하기(역순)
class ReverseNumericalOrder implements Comparator<Integer>{
	@Override
	public int compare(Integer arg0, Integer arg1) {
		return arg1 - arg0;
	}
}

 

---

버블정렬

배열에서 현재데이터(array[i])와 다음데이터(array[i+1]) 값의 크기를 계속 비교함. 더 이상 자리 교체가 없을때까지 반복한다.

소스코드로 구현하는 것은 간단하나 엄청나게 비효율적이다.

O(n²) : 역순으로 정렬된 데이터를 버블정렬할 경우의 성능. 루프를 돌때마다 하나의 값만 변경되기 때문이다

O(n) : 이미 정렬된 데이터를 버블정렬할 경우의 성능

 

package com.sort;

import org.junit.Test;

import static junit.framework.Assert.assertEquals;
import static org.junit.Assert.assertArrayEquals;

public class BubbleSort {

public void bubbleSort(int[] numbers) {
    boolean numbersSwitched;
    do {
        numbersSwitched = false;
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i + 1] < numbers[i]) {
                int tmp = numbers[i + 1];
                numbers[i + 1] = numbers[i];
                numbers[i] = tmp;
                numbersSwitched = true;
            }
        }
    } while (numbersSwitched);
}

    @Test
    public void testBubble() {
        final int[] numbers = {6, 4, 9, 5};
        final int[] expected = {4, 5, 6, 9};

        bubbleSort(numbers);
        assertArrayEquals(expected, numbers);
    }
}

 

 

---

삽입정렬

정렬된 데이터를 새로운 리스트에 담아서 반환한다.(새로운 리스트를 생성해서 반환)

이때, LinkedList로 반환. 링크드리스트는 리스트의 중간에 데이터를 추가하는 데 효율적. 포인터를 재배열하는 작업이 간단하기 때문이다.

- 버블정렬보다 좋은점 : 정렬이 끝나면 즉시 반환 가능. 버블정렬은 순서대로 리스트를 확인하느라 불필요한 연산을 진행한다

O(n²) : 이미 정렬된 리스트를 다시 삽입정렬한 경우의 성능. 매번 원소를 삽입할때마다 새 리스트의 끝까지 반복문을 실행한다.

O(n) : 역순으로 정렬된 리스트를 삽입정렬 한 경우의 성능. 해당 리스트앞에 있는 원소를 새리스트에 넣는다.

 

 

package com.sort;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import static junit.framework.Assert.assertEquals;

public class InsertSort {

public static List<Integer> insertSort(final List<Integer> numbers) {
    final List<Integer> sortedList = new LinkedList<>();

    originalList: for (Integer number : numbers) {
        for (int i = 0; i < sortedList.size(); i++) {
            if (number < sortedList.get(i)) {
                sortedList.add(i, number);
                continue originalList;
            }
        }
        sortedList.add(sortedList.size(), number);
    }

    return sortedList;
}

    @Test
    public void insertSort() {
        final List<Integer> numbers = Arrays.asList(6, 4, 9, 5);
        final List<Integer> expected = Arrays.asList(4, 5, 6, 9);

        final List<Integer> actual = insertSort(numbers);
        assertEquals(expected, actual);
    }
}

 

---

퀵 정렬

재귀적. 임의의 숫자(pivot)을 선정하여  pivot >=(크거나 같다), <(작다)로 두 가지로 분류한다

그리고 두 가지로 분류된 각 리스트는 다시 스스로를 정렬하는 메소드를 호출한다.

버블정렬, 삽입정렬보다 훨씬 효율적인 성능을 가진다. 데이터를 pivot을 기준으로 2개의 리스트로 분류하는 시간 복잡도는 O(n)이다.

각각의  재귀호출은 각 리스트 숫자의 절반만큼 발생한다. 따라서 퀵정렬 알고리즘의 평균적 성능은 O(n log n)이다.

 

package com.sort;


import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static junit.framework.Assert.assertEquals;

public class Quicksort {

public static List<Integer> quicksort(List<Integer> numbers) {
    if (numbers.size() < 2) {
        return numbers;
    }

    final Integer pivot = numbers.get(0);
    final List<Integer> lower = new ArrayList<>();
    final List<Integer> higher = new ArrayList<>();

    for (int i = 1; i < numbers.size(); i++) {
        if (numbers.get(i) < pivot) {
            lower.add(numbers.get(i));
        } else {
            higher.add(numbers.get(i));
        }
    }

    final List<Integer> sorted = quicksort(lower);

    sorted.add(pivot);
    sorted.addAll(quicksort(higher));

    return sorted;
}

    @Test
    public void testQuicksort() {
        final List<Integer> numbers = Arrays.asList(6, 4, 9, 5);
        final List<Integer> expected = Arrays.asList(4, 5, 6, 9);

        final List<Integer> actual = quicksort(numbers);
        assertEquals(expected, actual);
    }
}

---

병합정렬

분할정복 알고리즘(divide and conquer). 리스트를 두개로 나누고 각 하위 리스트를 정렬한 후 둘을 하나로 합친다.

 

package com.sort;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import static junit.framework.Assert.assertEquals;

public class Mergesort {

    public static List<Integer> mergesort(final List<Integer> values) {
        if (values.size() < 2) {
            return values;
        }

        final List<Integer> leftHalf =
                values.subList(0, values.size() / 2);
        final List<Integer> rightHalf =
                values.subList(values.size() / 2, values.size());

        return merge(mergesort(leftHalf), mergesort(rightHalf));
    }

    private static List<Integer> merge(final List<Integer> left,
                                       final List<Integer> right) {
        int leftPtr = 0;
        int rightPtr = 0;

        final List<Integer> merged =
                new ArrayList<>(left.size() + right.size());

        while (leftPtr < left.size() && rightPtr < right.size()) {
            if (left.get(leftPtr) < right.get(rightPtr)) {
                merged.add(left.get(leftPtr));
                leftPtr++;
            } else {
                merged.add(right.get(rightPtr));
                rightPtr++;
            }
        }

        while (leftPtr < left.size()) {
            merged.add(left.get(leftPtr));
            leftPtr++;
        }

        while (rightPtr < right.size()) {
            merged.add(right.get(rightPtr));
            rightPtr++;
        }

        return merged;
    }

    @Test
    public void testMergesort() {
        final List<Integer> numbers = Arrays.asList(6, 4, 9, 5);
        final List<Integer> expected = Arrays.asList(4, 5, 6, 9);

        final List<Integer> actual = mergesort(numbers);
        assertEquals(expected, actual);
    }
}