자료구조론 퀵정렬, 버블정렬, quick sort, bubble sort 퀵소트 버블소트

소개글

NodeSequence, ArraySequence를 이용하여 퀵소트 버블소트를 완성하기
중복을 허용하여 10개 정도 데이타셋을 선정하여 각 알고리즘이 stable한지 제시

n개의 원소로 이루어진 sorted dataset, random dataset, inverted dataset
을 임의로 설정하여 엑셀로 정렬시간도 비교한다.

각알고리즘에 우위비교도 행한다

엑셀로 비교그래프 하고, 보고서도 작성
C++로 작성하였습니다.

목차

실행모습
그래프
해당코드
참고문헌

본문내용

문제(8)의 pivot은 퀵소트가 왼쪽 부분 집합에는 기준 값보다 작은 원소들을 이동시키고, 오른쪽 부분집합에는 기준 값보다 큰 원소들을 이동시키므로 기준 값 pivot은 전체 원소 중에서 가운데(n/2)에 위치한 원소를 선택한다.

문제(9) 먼저 100개의 데이터만 놓고 비교해 볼 때 랜덤한 경우 버블소트가 퀵소트보다 시간이 오래 걸렸다. 1000개의 데이터 비교 시 랜덤한 경우, 순방향인 경우, 역방향인 경우 모두 퀵소트가 버블소트 보다 빨랐다. 2000개일 경우도 랜덤한 경우, 순방향인 경우, 역방향인 경우 모두 퀵소트가 버블소트 보다 빨랐다.

#ifndef NODE_LIST_H
#define NODE_LIST_H

#include "InvalidPositionException.h"
#include "EmptyContainerException.h"
#include "BoundaryViolationException.h"

template<typename Object>
class NodeList{
protected:
struct Node{//NodeList에 있는 노드
Object element;//원소
Node* prev;//앞 노드
Node* next;//뒷 노드
Node(const Object& e=Object(), Node* p=NULL, No
element(e),prev(p),next(n){}//생성자
};
typedef Node* NodePtr;//Node에의 포인터
public:
class Position{//NodeList의 위치
private:
NodePtr node; //노드에 대한 포인터
public:
Position(NodePtr n=NULL)//생성자
{node=n;}
Object& element() const //원소반환
throw(InvalidPositionException){
if(node==NULL) throw InvalidPositionException("Null position");
return node->element;
}
bool isNull() const//설 위치인가?
{return node==NULL;}
//
friend class NodeList<Object>;//접근허용
};

참고 자료

C++자료구조론, 이석호지음, 교보문고, 제7장 (정렬)
C,C++로 배우는 자료구조론, 김태헌, 한빛미디어, 제9장 (정렬 알고리즘과 효율)

압축파일 내 파일목록

보고서.hwp
알고리즘우위비교.xls
ArraySequence/12062820박경란ArraySequence.dsp
ArraySequence/12062820박경란ArraySequence.dsw
ArraySequence/12062820박경란ArraySequence.ncb
ArraySequence/12062820박경란ArraySequence.opt
ArraySequence/ArraySequence.h
ArraySequence/ArrayVector.h
ArraySequence/Debug/
ArraySequence/EmptyContainerException.cpp
ArraySequence/EmptyContainerException.h
ArraySequence/RuntimeException.cpp
ArraySequence/RuntimeException.h
NodeSequence/12062820.cpp
NodeSequence/12062820박경란_ListSequence.dsp
NodeSequence/12062820박경란_ListSequence.dsw
NodeSequence/12062820박경란_ListSequence.ncb
NodeSequence/12062820박경란_ListSequence.opt
NodeSequence/12062820박경란_ListSequence.plg
NodeSequence/BoundaryViolationException.cpp
NodeSequence/BoundaryViolationException.h
NodeSequence/EmptyContainerException.cpp
NodeSequence/EmptyContainerException.h
NodeSequence/InvalidPositionException.cpp
NodeSequence/InvalidPositionException.h
NodeSequence/NodeList.h
NodeSequence/NodeSequence.h
NodeSequence/RuntimeException.cpp
NodeSequence/RuntimeException.h
NodeSequence/Sort.h

전체 목록 보기