Juwan Park :: '정렬' 태그의 글 목록

퀵 정렬 (루비) 2편

루비로 퀵 정렬하기 1편에 이어서 포스팅합니다.원래는 사용자 함수 형태로 정의했지만, 이 포스트에서는 배열 클래스 안에 사용자정의 메소드 형태로 정의하는 방법입니다.다음 코드를 봅시다. class Array def quick_sort return self if self.length <= 1 # 배열의 원소 개수가 0이거나 1이면 그냥 그대로 돌려줌 begin pivot = (self.max + self.min) / 2 # 기준값을 최댓값과 최솟값의 중간으로 잡음 rescue pivot = self[rand(self.length)] # 예외 처리 발생시는 랜덤으로 함 end less = Array.new # 기준값보다 작은 원소들 equal = Array.new # 기준값과 같은 원소들 greater = ..

★프로그래밍/Ruby :: 2016.08.26 16:04

퀵 정렬 (루비) 1편

루비로 퀵 정렬 알고리즘을 구현한 예제입니다.여기서는 기존의 교환식 퀵 정렬 대신 병합식 퀵 정렬로 구현하였습니다. 이는 퀵 정렬에 병합 정렬 알고리즘을 접목시킨 것으로, 교환식 퀵 정렬의 단점이었던 불안정성(정렬 키 값이 같은 데이터끼리 순서가 정렬 후 서로 바뀔 수 있는 성질)을 해소하였습니다.코드는 다음과 같습니다. def quick_sort(a, randompivot = true) return a if a.length <= 1 # 배열의 원소 개수가 0이거나 1이면 그냥 그대로 돌려줌 pivot = a[randompivot ? rand(a.length) : 0] # 기준값을 랜덤으로 혹은 첫 번째 원소로 잡음 less = Array.new # 기준값보다 작은 원소들 equal = Array.new..

★프로그래밍/Ruby :: 2016.08.25 22:35

병합식 퀵 정렬

병합식 퀵 정렬 알고리즘에 대해 포스팅합니다.이를 이해하려면 먼저 퀵 정렬이라는 알고리즘에 대해 이해할 필요가 있습니다.우선 우리가 흔히 알고 있는 퀵 정렬은 버블 정렬처럼 데이터의 값을 서로 바꾸는 '교환 정렬' 방식입니다. 여기서는 교환식 퀵 정렬이라고 부르겠습니다.먼저 교환식 퀵 정렬이 어떻게 돌아가는지 보자면, [4, 6, 1, 7, 8, 2, 3, 5] 이렇게 뒤죽박죽이 된 배열이 있다고 했을 때, 맨 앞의 4를 기준값으로 잡은 후 한 번 돌려 봅시다. [4, 6, 1, 7, 8, 2, 3, 5] P > [3, 6, 1, 7, 8, 2, 4, 5] < P [3, 4, 1, 7, 8, 2, 6, 5] P > [3, 2, 1, 7, 8, 4, 6, 5] < P [3, 2, 1, 4, 8, 7, 6,..

★프로그래밍 :: 2016.08.25 22:00

병합 정렬 (파이썬)

파이썬으로 병합 정렬 알고리즘을 구현한 예제입니다. 병합 정렬에 대한 설명은 이미 루비로 병합 정렬 구현하기 포스트에서 했으니 여기서는 따로 하지 않겠습니다. 코딩 구조를 보면 루비와 비슷하다고 느껴질 수도 있겠으나 둘은 엄연히 다른 언어입니다. 파이썬 병합 정렬 코드를 일단 짜 보자면... def merge_sort(a): if len(a) <= 1: return a # 배열 개수가 1 이하이면 그냥 리턴, 아니면 계속 진행 half = len(a) // 2 # 개수에서 2를 나눔 (소수점 버림) L = merge_sort(a[:half]) # 왼쪽은 앞의 반만 R = merge_sort(a[half:]) # 오른쪽은 앞의 반 제외 mer = [] # 정렬 결과 저장될 배열 while len(L) > ..

★프로그래밍/Python :: 2016.08.25 20:26

병합 정렬 (루비)

루비에서 병합 정렬 알고리즘을 구현한 예제입니다. 우선 병합 정렬의 개념에 대해 먼저 설명드리자면, 정렬을 수행한 데이터를 반씩 쪼갠 다음 정렬 과정에서 다시 붙여나가는 정렬 방식입니다. 예를 들어, 배열 [4, 1, 2, 3]이 있다고 합시다. 그러면... 이 배열을 정렬하기 위해 반으로 쪼개 [4, 1] [2, 3]으로 만듭니다. 그리고 [4, 1]을 다시 쪼개 [4] [1]로 만들면, [4]는 원소가 하나이므로 더는 쪼갤 수 없고 [1]도 마찬가지로 더는 쪼갤 수 없습니다. 그러므로 이 둘의 값을 비교하여 정렬합니다. 1이 4보다 작으므로 당연히 1이 앞에 옵니다. 정렬되면서 4와 1로 쪼개진 게 다시 [1, 4]로 합쳐졌습니다.위 1번에서 쪼갠 나머지 반쪽인 [2, 3]도 위 2번~3번과 같은 방..

★프로그래밍/Ruby :: 2016.08.25 12:36

.sort 메소드로 안정 정렬 구현하기

정렬 알고리즘에 대해 공부하다 보면 안정 정렬(stable sort)과 불안정 정렬(unstable sort)에 대해 들어 보신 적이 있을 것입니다. 이 둘의 차이가 무엇인지를 일단 간단히 설명드리자면, 정렬 키 값이 같은 데이터들에 대해 정렬 전의 순서가 정렬 후에도 유지될 것이 보장되면 안정 정렬이라고 하고, 키 값이 같은 데이터들의 순서가 정렬 후 서로 바뀔 가능성이 있으면 불안정 정렬이라고 합니다.예를 들어, 배열이 [4, 4, 1, 6, 7, 9, 5, 8, 3, 2] 이렇게 처음에 똑같은 4가 두 개 있을 때 첫 번째 4가 정렬 후에도 항상 두 번째 4보다 앞에 있게 되면 안정 정렬이고, 첫 번째 4가 정렬 후에 두 번째 4보다 뒤로 갈 가능성이 있으면 불안정 정렬입니다. 그러면, 루비의 .s..

★프로그래밍/Ruby :: 2016.08.24 17:22

.sort 메소드 관련 보충 포스팅

이전에 루비에서 배열 정렬에 사용되는 .sort 메소드에 대해 포스팅을 했습니다.이 포스트에서는 시간관계상 쓰지 못했던 내용에 대해 보충합니다.자, 먼저 2차원 배열의 정렬 예입니다. gfriend = Array.new gfriend << ["예린", "1996-08-19"] gfriend << ["엄지", "1998-08-19"] gfriend << ["신비", "1998-06-03"] gfriend << ["소원", "1995-12-07"] gfriend << ["은하", "1997-05-30"] gfriend << ["유주", "1997-10-04"] gfriend.sort! gfriend.each_index do |x| puts sprintf("%s", gfriend[x]) end 걸그룹 여자친구..

★프로그래밍/Ruby :: 2016.08.24 12:40

.sort - 배열의 값을 정렬하는 메소드

루비에서 사용하는 배열에는 특징이 있습니다.그 특징들 중 하나로, 자체적인 정렬 메소드를 제공한다는 점입니다.흔히 정렬 하면 정렬 알고리즘을 코드에 짜 넣는 경우가 일반적이지만, 루비에서는 정렬 메소드를 제공함으로써 배열의 정렬 알고리즘을 코딩하는 수고를 덜 수 있습니다.일단 다음 코드를 봅시다. arr = [4, 1, 2, 5, 3] (arr.length - 2).downto(0) do |x| 0.upto(x) do |y| arr[y], arr[y+1] = arr[y+1], arr[y] if arr[y] > arr[y+1] end end puts sprintf("%s", arr) 이 코드를 실행하면 맨 처음 [4, 1, 2, 5, 3]으로 세팅된 배열 arr를 오름차순 정렬하여 [1, 2, 3, 4, ..

★프로그래밍/Ruby :: 2016.08.24 00:03
Today 6    Yday 29    Tot 67,005
Juwan Park
Juwan Park's blog is powered by Daum and TISTORY.
Contemporary Blue for TISTORY.
Designed by Juwan Park. Creative Commons License
▲ TOP