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

거품 정렬 (Bubble Sort) [C++ 소스]

언제나휴일 2016. 5. 19. 23:43
반응형

거품 정렬 (Bubble Sort) [C++ 소스]


2.2 거품 정렬.zip

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


//Program.cpp

#include "common.h"

 

template <typename data, typename compare>

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

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

{

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

    {

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

        {

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

            {

                swap(base[j-1], base[j]);//교환(base[j-1],base[j])

            }

        }

    }

}

 

 

#define MAX_DATA 1000

 

int main()

{

    Member *base[MAX_DATA];

    MakeRandomMembers(base,10);

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

    ViewMembers(base,10);

    bubble_sort(base,10,CompareByNum);

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

    ViewMembers(base,10);

    bubble_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();   

    bubble_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);

    bubble_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

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



반응형