알고리즘/정렬
-
[알고리즘]-[정렬]-퀵정렬(JAVA)알고리즘/정렬 2018. 10. 30. 18:41
퀵정렬 (quick sort)개념 원소를 하나 정하여(여기서는 배열의 맨 앞 요소를 기준으로 정함) 이 원소를 pivot 이라 지칭하고 pivot 보다 작거나 같은 수들과 큰 수들을 좌우로 나누면서 정렬하는 방식pivot 의 위치는 정렬 후의 위치로 확정된다.pivot의 왼쪽과 오른쪽의 자리는 바뀌지 않는다. 왼쪽은 pivot 보다 무조건 작거나 같은 원소들, 오른쪽은 pivot 보다 무조건 큰 원소들이 위치한다.재귀함수 디자인의 과정작성하려는 함수의 역할을 말로 명확하게 정의한다. 1234 // arr을 start 부터 end 까지 퀵정렬하는 함수 public void quickSort(int arr[], int start, int end) { }Colored by Color Scriptercs 함수가..
-
[알고리즘]-[정렬]-합병정렬(JAVA)알고리즘/정렬 2018. 10. 30. 15:53
합병정렬 (merge sort)개념배열을 절반으로 나누어 각각을 정렬한 후, 합치는 정렬 알고리즘시간 복잡도는 O(n log n) 이다. 처리과정정렬을 해야할 배열을 절반으로 나누어 왼쪽 배열 오른쪽 배열을 정렬한다.정렬된 왼쪽 배열 오른쪽 배열을 순서대로 합친다.위의 처리과정을 크게 두가지로 나눌 수 있다. 그럼.. 첫번째 순서에서 절반으로 나뉘어진 왼쪽 배열 오른쪽 배열의 정렬을 어떻게 정렬 할것인가? 라는 의문이 생기는데그 절반으로 나뉘어진 두 배열도 똑같이 또 절반으로 나누고 정렬된 배열을 순서대로 합치면 된다.그렇다는것은 재귀적으로 절반으로 나뉘어지지 않을때까지 배열이 나뉘어질 것이고 그 순간부터 하나하나 나뉘어진 배열을 합치면서 정렬이 진행된다. 정확한 순서는 아래 애니메이션을 보면 코드는 감..
-
[알고리즘]-[정렬]-삽입정렬 (JAVA)알고리즘/정렬 2018. 10. 30. 12:12
삽입정렬(insertion sort)개념배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 정렬 알고리즘 이다.정렬의 시작은 두번째 요소부터 시작되며 본인의 왼쪽으로는 이미 정렬된 상태라 생각하면 된다.왼쪽의 값이 비교하려는 요소값보다 작을떄까지 위치를 왼쪽으로 이동시키면 된다.처리과정정렬의 시작은 두번째 요소인 4부터 왼쪽의 값들과 비교를 하면된다.처음은 비교할 값이 14 하나 뿐이고 4가 14보다 작기떄문에 값을 서로 교체한다. 4와 14는 이미 정렬이 됐고 정렬할 다음 요소는 세번째 요소인 8이다. 같은 방법으로 왼쪽의 정렬된 요소들과 비교를 하여 자기 위치를 찾아가면 된다.자세한 처리과정은 아래 애니메이션을 참고하면 된다. 소스 (JAVA)1234..
-
[알고리즘]-[정렬]-선택정렬(JAVA)알고리즘/정렬 2018. 10. 30. 11:19
선택정렬개념최소값을 앞으로 이동시키며 정렬하는 방식. (오름차순 기준)주어진 배열에서 최소값을 찾는다.찾은 최소값을 배열의 맨 앞에 위치한 값과 교체한다.맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 처리과정 선택정렬을 인덱스가 중요한데 최소값을 인덱스를 0부터 마지막 인덱스까지 증가 시키면서 최소값을 해당 인덱스의 값과 교체하면 된다.위의 배열에서 최소값을 찾으면 7번 인덱스에 값 2가 최소값인걸 확인 할 수 있다.이 값을 0번 인덱스의 값 14와 교체 한다. 기준점이 되는 인덱스를 1 올리고 그 다음 최소값을 찾아 같은 방법으로 정렬을 시작한다.자세한 과정은 애니메이션을 확인해보면 알 수 있다. 소스 (JAVA)1234567891011121314151617public int[] getS..
-
[알고리즘]-[정렬]-버블정렬(JAVA)알고리즘/정렬 2018. 10. 29. 18:07
버블정렬 (Bubble Sort) 개념인접한 두 원소를 비교하여 큰 수를 뒤로 보내는 알고리즘 이다. 시간 복잡도는 O(n^2) 의 시간 복잡도를 가지며 정렬 알고리즘 처리속도가 제일 느리다.장점은 코드가 단순해서 구현하기가 편하고 자주 사용된다.단점은 처리속도가 느리다. 처리속도가 느리기 때문에 용량이 큰 리스트를 정렬할 때는 적합하지 않다. 처리과정 위와 같이 길이가 10인 {14, 4, 8, 23, 11, 5, 3, 2, 4, 9} 정수형 배열이 존재하고 이 배열을 버블 정렬로 정렬을 하고자 하면 0번째 인덱스에서 배열의 길이만큼 반복문을 돌면서 (i) 와 (i+1) 인덱스의 값을 비교하고( i ) 인덱스의 값이 (i + 1) 인덱스의 값 보다 크다면 ( i ) 인덱스와 ( i + 1 ) 인덱스의 ..