221115 정렬알고리즘

선택 정렬 O(N^2)

(오름차순 정렬 시)데이터가 무작위로 있을 때,

가장 작은 데이터를 맨 앞과 바꾸고

그 다음 작은 데이터를 앞에서 2번째와 바꾼다. -> 이 것을 계속해서 반복하여 정렬

 

삽입정렬 O(N^2)

(오름차순 정렬 시)데이터가 무작위로 있을 때,

2번 째 데이터를 1번 째 데이터의 왼쪽으로 보낼지 오른쪽으로 보낼지를 (데이터 크기 비교 후) 결정한다

3번째 데이터를 2번째 데이터와 1번째의 데이터 값을 보고 어디로 보낼지 결정한다.

위를 반복하는데

특징으로는 나보다 작은 숫자를 만나게 되면 거기서 부터의 왼쪽 숫자들은 고려야 할 필요가 없다는 것

 

퀵 정렬 O(NLogN), 가장 많이 쓰임

(오름차순 정렬 시)데이터가 무작위로 있을 때,

리스트의 첫 번째 데이터를 피벗으로 두고

왼쪽에선 피벗보다 큰 데이터를 찾고, 오른쪽에서 피벗보다 작은 데이터를 찾는다 -> 찾으면 서로 위치를 바꾼다.

반복하여 진행하다 왼쪽에서부터 찾은 데이터랑, 오른쪽에서부터 찾은 데이터가 서로 (교차 후 = 엇갈리게) 지나가게 되면

오른쪽에서 부터 찾은 데이터(피벗보다 작은 수)와 피벗 위치를 바꾼다.

 

피벗 왼쪽의 수들은 피벗보다 작은 수가 위치, 피벗 오른쪽 수들은 피벗보다 큰 수가 위치하게 된다.

이 작업을 분할(divide) or 파티션(partition)이라 한다.

이제 왼쪽, 오른쪽 분할 된 파트를 다시 퀵정렬 반복을 진행한다.

 

계수정렬 O(N+K)

특정제한조건에서만 사용하는 정렬로 속도가 매우 빠르다

0~9까지의 양의 정수가 무작위로 주어졌을 때 (오름차순 정렬시)

int[10] list 생성 한 뒤(0~9 양의 정수를 표현하려면 10개 여야함), 무작위로 주어진 수를 하나씩  읽고 그에 해당하는 값을 List에서의 인덱스에 맞춰 +1을 해주면 된다.

(예를들면 수가 0이면 리스트의 1번째 값을 +1 해준다, 수가 9면 리스트의 10번 째 값을 +1)

리스트의 인덱스에 적힌 숫자대로 0~9를 찍어내면 정렬이 된다.

 

한마디로 무작위 나열된 숫자들을 읽고 호출된 숫자 빈도 수를 다 리스트에 저장 한뒤,

리스트의 인덱스 순으로 그저 찍어내면 정렬이 되는 것이다.  

 

https://st-lab.tistory.com/243 

익명함수에 대해서

익명함수란?

public class Anonymous {
	public static void main(String[] args) {
 
		Rectangle a = new Rectangle();
		
		Shape anonymous = new Shape() {
			int depth = 40;
			
			@Override
			public int get() {
				return width * height * depth;
			}
		};
 
		System.out.println(a.get());		// Shape 인터페이스를 구현한 Rectangle
		System.out.println(anonymous.get());	// Shape 인터페이스를 구현한 익명 객체
	}
 
}
 
class Rectangle implements Shape {
	int depth = 40;
	
	@Override
	public int get() {
		return width * height * depth;
	}
}
 
interface Shape {
 
	int width = 10;
	int height = 20;
 
	int get();
}

 

Comparable과 Comparator에 대해서

Comparable과 Comparator의 차이

Comparable 인터페이스에는 compareTo(T o) 메소드 하나가 선언
Comparator 인터페이스는 많은 메소드 선언 그러나 사용은 compare(T o1, T o2)

 Comparable  compareTo(T o) 메소드는 "자기 자신과 매개변수 객체를 비교"
 Comparator  compare(T o1, T o2)메소드는 "들어오는 두 매개변수 객체를 비교

public class Test {
	public static void main(String[] args) {
    
		// 익명 객체 구현방법 1
		Comparator<Student> comp1 = new Comparator<Student>() {
			@Override
			public int compare(Student o1, Student o2) {
				return o1.classNumber - o2.classNumber;
			}
		};
	}
 
	// 익명 객체 구현 2
    // -1,0,1 반환으로 할 것
	public static Comparator<Student> comp2 = new Comparator<Student>() {
		@Override
		public int compare(Student o1, Student o2) {
			return o1.classNumber - o2.classNumber;
		}
	};
}
 
 
// 외부에서 익명 객체로 Comparator가 생성되기 때문에 클래스에서 Comparator을 구현 할 필요가 없어진다.
class Student {
 
	int age;	    // 나이
	int classNumber;// 학급
	
	Student(int age, int classNumber) {
		this.age = age;
		this.classNumber = classNumber;
	}
 
}

 

Java에서의 정렬은 특별한 정의가 되어있지 않는 한 '오름차순'을 기준

즉, compare 혹은 compareTo를 사용하여 객체를 비교 할 경우 음수가 나오면 두 원소의 위치를 바꾸지 않는다는 것

 

Arrays.sort로 객체 사용예제
Comparable

public class Test {
	
	public static void main(String[] args) {
		
		MyInteger[] arr = new MyInteger[10];
		
		// 객체 배열 초기화 (랜덤 값으로) 
		for(int i = 0; i < 10; i++) {
			arr[i] = new MyInteger((int)(Math.random() * 100));
		}
 
		// 정렬 이전
		System.out.print("정렬 전 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
        
		
        //////////////////////////사용모습
		Arrays.sort(arr);
        //////////////////////////
        
      
        
		// 정렬 이후
		System.out.print("정렬 후 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
	}
	
}
 
class MyInteger implements Comparable<MyInteger> {
	int value;
	
	public MyInteger(int value) {
		this.value = value;
	}
	
	@Override
	public int compareTo(MyInteger o) {
		return this.value - o.value;
	}
	
}

 

 

Arrays.sort / comparator 사용모습

public class Test {
	
	public static void main(String[] args) {
		
		MyInteger[] arr = new MyInteger[10];
		
		// 객체 배열 초기화 (랜덤 값으로) 
		for(int i = 0; i < 10; i++) {
			arr[i] = new MyInteger((int)(Math.random() * 100));
		}
 
		// 정렬 이전
		System.out.print("정렬 전 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
		
        ///////////////이런식으로 사용
		Arrays.sort(arr, comp);		// MyInteger에 대한 Comparator을 구현한 익명객체를 넘겨줌
        //////////////
        
        
		// 정렬 이후
		System.out.print("정렬 후 : ");
		for(int i = 0; i < 10; i++) {
			System.out.print(arr[i].value + " ");
		}
		System.out.println();
	}
 
	
	static Comparator<MyInteger> comp = new Comparator<MyInteger>() {
		
		@Override
		public int compare(MyInteger o1, MyInteger o2) {
			return o1.value - o2.value;
		}
	};
}
 
 
class MyInteger {
	int value;
	
	public MyInteger(int value) {
		this.value = value;
	}
	
	
}