[알고리즘/계수정렬(Counting Sort)] - 자바
계수정렬에 대해 알아보자 지난 포스팅에서 대부분의 sort알고리즘을 살펴보았는데요. 그 중 빠르다고 할 수 있는 알고리즘은 O(NlogN)의 속도를 자랑하는 퀵정렬,병합정렬이 있죠. 하지만 특정한 경우에 이 알고리즘들 보다도 더 빠른 알고리즘이 존재합니다. 무려 O(N)의 속도를 보입니다. 바로 계수정렬(Counting Sort)인데요. 이름만 봐도 아시겠지만 맞습니다. 세는거에요! [6,3,5,4,8,4,0,3,4,8,0,5,3,2,5,7,8,3,1,2,4] 이러한 데이터가 있다고 가정했을 때 가장 큰 값이 8 작은 값이 0입니다. 이 데이터를 정렬한다고 할게요. 0~8의 인덱스를 가지는 1차 배열을 선언해주고 데이터를 돌아가면서 각 인덱스에 값을 1씩 ++해줍니다. 맞습니다 개수를 세는거에요. 그렇게..
알고리즘의 시작 정렬 알고리즘(sort Algorithm) 4. 퀵 정렬
안녕하세요 오늘은 퀵정렬입니다. 이름에도 써 있듯 퀵(quick)하게 정렬 됩니다. 이해하는데 한참 걸렸어요 ㅜㅜ 시작해보겠습니다. 퀵정렬 분할해서 정렬한다고 생각하시면 되는데 [1,10,5,8,7,6,4,3,2,9] 퀵정렬에서는 피봇값을 하나 잡습니다. 여기서는 첫번째 것을 잡아볼게요 [1,10,5,8,7,6,4,3,2,9] 왼쪽에는 아무것도 없으니 그대로 두고 오른쪽 부분에서 오른쪽으로 이동하면서 나보다 큰값을 찾고 왼쪽으로 이동하면서 나보다 작은 값을 찾습니다. [1,10,5,8,7,6,4,3,2,9] 나보다 큰 값은 10이 될 것이고 작은 값은 없고 다시 나에게로 오게 됩니다. 이렇게 엇갈렸을 때는 작은 값과 피봇값을 바꿔 줍니다. 자기 자신을 바꾸는 것이니 그대로 [1,10,5,8,7,6,4,3..
알고리즘의 시작 정렬 알고리즘(sort Algorithm) 3. 삽입 정렬
세 번째 시간입니다. 오늘은 삽입 정렬 가지고 왔습니다. 마지막에 앞서서 봤던 선택, 버블 정렬과 오늘 볼 삽입 정렬들을 비교 해보겠습니다ㅎ 삽입 정렬 삽입 정렬은 앞선 정렬들 보다는 더 나은(?) 정렬 알고리즘이라고 볼 수 있는데요. 삽입정렬은 말 그대로 각 숫자를 들어가야 할 곳에 삽입하는 알고리즘입니다. [2,7,4,6,8,10,5,1,3,9] 자 똑같은 데이터가 있습니다. 처음으로 인덱스 1에 있는 숫자를 가지고 왼쪽의 있는 수 와 비교합니다. [2,7,4,6,8,10,5,1,3,9] 그 자리에 그대로 있겠네요. 인덱스 2에 있는 수와 왼쪽의 있는 데이터들과 비교하면 들어갈 자리가 명확하죠. [2,4,7,6,8,10,5,1,3,9] 이런 식으로 [2,4,6,7,8,10,5,1,3,9] [2,4,6..
알고리즘의 시작 정렬 알고리즘(sort Algorithm) 2. 버블 정렬
두번째 시간입니다. 오늘은 버블정렬 가지고 왔습니다. 버블정렬 버블정렬 또한 선택정렬과 같이 굉장히 직관적인 정렬 방법입니다. 바로 옆의 데이터와 비교해서 더 작은 값을 앞으로 보내자! 입니다. [2,7,4,6,8,10,5,1,3,9] 자 전 시간과 같은 데이터가 있습니다. 맨 앞의 0,1 번째 데이터를 비교하면 [2,7,4,6,8,10,5,1,3,9] 변하질 않네요 다음 1,2번째 비교하면 [2,4,7,6,8,10,5,1,3,9] [2,4,6,7,8,10,5,1,3,9] [2,4,6,7,8,10,5,1,3,9] [2,4,6,7,8,10,5,1,3,9] [2,4,6,7,8,5,10,1,3,9] . . . 이런식으로 변화하게 됩니다. 그럼 결국 첫번째 비교가 끝나면 가장 큰 값인 10이 오른쪽 끝으로 가겠..
