C++/디딤돌 자료구조와 알고리즘 with C++

선택 정렬(Selection Sort) [C++ 소스]

언제나휴일 2016. 6. 10. 13:40
반응형

선택 정렬(Selection Sort) [C++ 소스]


2.3 선택정렬.zip


"본문 내용"은 언제나 휴일 본 사이트에 있습니다.


//Program.cpp

#include "common.h"

 

template <typename data, typename compare>

//선택 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리)

void selection_sort(data *base, size_t n, compare com)

{

    for(size_t i=0; i<n; i++)//반복(i:=0->n)

    {

        size_t min = i;//min=i

        for(size_t j=i+1; j<n; j++) //반복(j:=i+1->n)

        {

            if(com(base[min],base[j])>0)//조건(compare(base[min], base[j]) > 0)

            {

                min = j;//min := j

            }

        }

        swap(base[i],base[min]);//교환(base[i],base[min])

    }

}

#define MAX_DATA 1000

 

int main()

{

    Member *base[MAX_DATA];

    MakeRandomMembers(base,10);

    cout<<"정렬 전"<<endl;

    ViewMembers(base,10);

    selection_sort(base,10,CompareByNum);

    cout<<"번호로 정렬 후"<<endl;

    ViewMembers(base,10);

    selection_sort(base,10,CompareByName);

    cout<<"이름으로 정렬 후"<<endl;

    ViewMembers(base,10);

    RemoveMembers(base,10);

 

    clock_t st,et;

 

    MakeRandomMembers(base,MAX_DATA);

    cout<<"수행 성능 테스트1 자료 개수:"<<MAX_DATA<<endl;

    st = clock();   

    selection_sort(base,MAX_DATA,CompareByName);   

    et=clock();

    cout<<"수행 속도:"<<et-st<<endl;

    RemoveMembers(base,MAX_DATA);

 

    MakeRandomMembers(base,MAX_DATA/10);

    cout<<"수행 성능 테스트2 자료 개수:"<<MAX_DATA/10<<endl;

    st = clock();

    MakeRandomMembers(base,MAX_DATA/10);

    selection_sort(base,MAX_DATA/10,CompareByName);

    et=clock();

    cout<<"수행 속도:"<<et-st<<endl;

    RemoveMembers(base,MAX_DATA/10);

    return 0;

}

 


//common.h

#pragma once

#include <stdio.h>

#include <stdlib.h>

#include <iomanip>

#include <iostream>

#include <string>

#include <time.h>

using namespace std;

 

class Member

{

    string name;

    int num;

public:

    Member(string name,int num)

    {

        this->name = name;

        this->num = num;

    }

    string GetName()const

    {

        return name;

    }

    int GetNum()const

    {

        return num;

    }

    void View()const

    {

        cout<<setw(10)<<setfill('0')<<num<<","<<name<<endl;

    }

};

 

int CompareByNum(Member *m1, Member *m2)

{

    int n1 = m1->GetNum();

    int n2 = m2->GetNum();

    return  n1 - n2;

}

int CompareByName(Member *m1, Member *m2)

{

    string n1 = m1->GetName();

    string n2 = m2->GetName();

    return  n1.compare(n2);

}

 

void MakeRandomMembers(Member **pbase, size_t n)

{

    for(size_t i=0; i<n; i++)

    {

        int num = rand()*rand();

        char buf[256];

        sprintf_s(buf,sizeof(buf),"이름%010d",rand()*rand());

        pbase[i] = new Member(buf,num);

    }

}

 

void RemoveMembers(Member **pbase, size_t n)

{

    for(size_t i=0; i<n; i++)

    {       

        delete pbase[i];

    }

}

 

void ViewMembers(Member **pbase, size_t n)

{

    for(size_t i=0;i<n; i++)

    {

        pbase[i]->View();

    }

}


▷실행 결과

정렬 전

0000757147,이름0167851000

0301413356,이름0336971124

0659598368,이름0160567225

0391749387,이름0004890851

0035766290,이름0026239572

0473038164,이름0000597006

0003615544,이름0326051436

0392289610,이름0118341522

0170427798,이름0037215528

0675016433,이름0168544290

번호로 정렬 후

0000757147,이름0167851000

0003615544,이름0326051436

0035766290,이름0026239572

0170427798,이름0037215528

0301413356,이름0336971124

0391749387,이름0004890851

0392289610,이름0118341522

0473038164,이름0000597006

0659598368,이름0160567225

0675016433,이름0168544290

이름으로 정렬 후

0473038164,이름0000597006

0391749387,이름0004890851

0035766290,이름0026239572

0170427798,이름0037215528

0392289610,이름0118341522

0659598368,이름0160567225

0000757147,이름0167851000

0675016433,이름0168544290

0003615544,이름0326051436

0301413356,이름0336971124

수행 성능 테스트1 자료 개수:1000

수행 속도:4357

수행 성능 테스트2 자료 개수:100

수행 속도:36


프로그래밍 언어 및 기술 학습, 무료 동영상 강의 언제나 휴일


반응형