[논문]정보 블록 정렬 알고리즘에 관한 연구

송태옥

정보 블록 정렬 알고리즘에 관한 연구
A Study on Information Block Sort Algorithm 원문보기

본 논문에서는 O(NlogN) 의 시간 복잡도와 데이터의 분포상태에 영향을 받지 않는 정보블록 정렬알고리즘(IBSA : Information Block Sort Algorithm)을 제안하고, 시뮬레이터를 이용하여 그 성능을 평가하였다. 2백만 개의 랜덤 데이터를 이용하여 IBSA의 성능을 측정해본 결과, 퀵 정렬의 22%, 개선된 퀵 정렬의 36% 정도의 비교회수만으로도 정렬할 수 있음을 보여주었다.

In this paper, I proposed a sort algorithm named Information Block Sort Algorithm(IBSAl which is not influenced on distribution of data in the list and has time complexity of O(NlogN). Also I evaluated the IBSA using a simulator. Performance analysis shows that, in case of sorting randomly generated two millions data, the number of actual comparisons has taken place about 36% of the number of comparisons in the improved Quick sort algorithm and 22% in Quick sort algorithm.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

제시하였다. 그리고 결론과 향후 연구 과제를 기술하였다.
본 연구는 이러한 연구의 일부분으로서, 정보 블록 정렬 알고리즘(IBSA : Information Block Sort Algorithm)이라는 새로운 정렬 알고리즘을 제안하고자 한다.
본 연구에서는 O(NlogN)으' 시간 복잡도와 데이터의 분포상태에 영향을 받지 않는 정보 블록 정 렬알고리즘을 제안하고, 그 성능을 평가하였다. IBSA의 성능올 측정해본 결과, 2백만 개의 랜덤 데이터를 정렬한 경우, 퀵 정렬의 약 20% 정도의 비교회수만으로도 정렬할 수 있음을 보여주었다.
첫째로는, IBSA의 성능을 높이기 위하여 알고리즘의 핵심요소인 블록 데이터 범위(BDR)와 정보 블록의 개수(M)의 최적화에 대한 연구이며, 둘째로는, IBSA 역시 분할 정렬 알고리즘이기 때문에 외부 정렬 기법과의 연동 그리고 멀티프로세서를 이용하는 병렬처리 시스템의 정렬에서도 유용할 것으로 생각되므로 이에 관한 연구를 하는 것이다.

가설 설정

1) 리스트의 초기 상태는 다음과 같으며, BDP (▲)는 Temp로 이동한 데이터가 없으므로 어떤 위치도 가리키지 않는다.

제안 방법

IBSA와 비교할 알고리즘은 퀵 정렬 알고리즘과 개선된 퀵 정렬 알고리즘 두 가지로서, 알고리즘과 시간 복잡도를 중심으로 살펴보았다.
본 연구에서 제안하는 IBSA의 성능을 일반적으로 빠른 정렬 알고리즘이라고 알려진 퀵 정렬 [1, 3, 5, 6] 알고리즘 그리고 개선된 퀵 정렬 알고리즘[4]과 비교하고자한다.
실험에 이용될 데이터는 두 가지로써, 현재 시각을 기초로 생성되어 균등한 분포를 보이는 난수, 그리고 가우스 함수를 이용해 정규 분포를 보이는 난수를 이용한다. 이와 같이 데이터를 두 가지로 선정한 이유는 실험 데이터가 특정 범위에 데이터가 집중되는 정규 분포의 경우, 알고리즘의 성능 저하를 초래할 수 있기 때문이다.
아래에 나올 내용은 먼저 IBSA의 알고리즘을 분석한 후, 성능 비교를 위한 실험결과를 그래프로 제시하였다. 그리고 결론과 향후 연구 과제를 기술하였다.

대상 데이터

② 실험데이터는 시각을 기초로 생성되어 균일 분포를 보이는 난수 그리고 가우스 함수를 이용해 정규분포를 보이는 난수, 이두 가지 데이터를 이용한다.
두 번째 실험 데이터는 가우스 함수를 이용해 생성된 정규 분포를 나타내는 데이터로서, 이 데이터를 5000이라는 범위로 그룹을 묶어 데이터의 분포를 (그림 6)에 나타내었다.
첫 번째 실험 데이터는 균등한 분포를 띄는 데이터로서, 이 데이터를 5000이라는 범위로 그룹을 묶어 데이터의 분포를 (그림 5)에 나타내었다.

성능/효과

평가하였다. IBSA의 성능올 측정해본 결과, 2백만 개의 랜덤 데이터를 정렬한 경우, 퀵 정렬의 약 20% 정도의 비교회수만으로도 정렬할 수 있음을 보여주었다.
비교회수 면에서 IBSA는 퀵 정렬의 22%, 개선된 퀵 정렬의 36% 정도의 비교회수만으로 정렬올 완료할 수 있었다. 그리고 개선된 퀵 정렬 알고리즘은 퀵 정렬 알고리즘에 비해 40% 가량 성능이 우수한 것으로 나타났다.
둘째, 데이터가 특정 범위에 밀집되는 가우스분포를 보이는 경우에도 IBSA의 성능 저하는 없다는 점이다. 이 점은 IBSA의 최악과 평균 시간복잡도를 대변해주는 것으로서, 정렬의 안정성을 보여주고 있다.
비교회수 면에서 IBSA는 퀵 정렬의 22%, 개선된 퀵 정렬의 36% 정도의 비교회수만으로 정렬올 완료할 수 있었다. 그리고 개선된 퀵 정렬 알고리즘은 퀵 정렬 알고리즘에 비해 40% 가량 성능이 우수한 것으로 나타났다.
비교회수가 N?에 비례하는 최악의 경우가 발생할 확률을 낮추어준다는 것, 둘째 분할을 위해 키를 사용할 필요가 없다는 것, 셋째 전체 수행 시간이 기존의 퀵 정렬에 비해 20~25% 정도 빠르다는 것을 들 수 있다.
첫째, IBSA는 정규 분포를 보이는 데이터의 정렬뿐만 아니라 균등 분포를 보이는 데이터의 정렬에서도 퀵 정렬과 개선된 퀵 정렬 알고리즘에 비해 상당히 효과적인 알고리즘이라는 점이다. 비교회수 면에서 IBSA는 퀵 정렬의 22%, 개선된 퀵 정렬의 36% 정도의 비교회수만으로 정렬올 완료할 수 있었다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

정보 블록 정렬 알고리즘에 관한 연구
A Study on Information Block Sort Algorithm 원문보기

초록
AI-Helper

Abstract ▼ AI-Helper

AI 본문요약
AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

정보 블록 정렬 알고리즘에 관한 연구 A Study on Information Block Sort Algorithm 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

Abstract ▼ AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

가설 설정

제안 방법

대상 데이터

성능/효과

이 논문을 인용한 문헌

저자의 다른 논문 :

송태옥 (2)

관련 콘텐츠

원문 보기

원문 URL 링크

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

정보 블록 정렬 알고리즘에 관한 연구
A Study on Information Block Sort Algorithm 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper