[강의] 11월 29일 수업정리

heap 알고리즘과  퀵정렬에 대한 수업을 들었다.

 

 

1. HEAP 알고리즘

#include "heap.h"

void C_HEAP::swap(int& nDst, int& nSrc)
{
    int nTmp = nDst;
    nDst = nSrc;
    nSrc = nTmp;
}

void C_HEAP::up(int nCurrent, int nParent)
{
    if (nParent == 0 || m_arData[nCurrent] >= m_arData[nParent])
        return;

    swap(m_arData[nCurrent], m_arData[nParent]);
    up(nParent, nParent / 2);
}

bool C_HEAP::add(const int& nData)
{
    if (m_nLastIndex + 1 == 11)
        return false;

    m_nLastIndex++;
    m_arData[m_nLastIndex] = nData;

    up(m_nLastIndex, m_nLastIndex / 2);

    return true;
}

bool C_HEAP::top(int& nData)
{
    if (m_arData[m_nLastIndex = 0])
        return false;

    nData = m_arData[1];
    return true;
}

void C_HEAP::pop()
{
    if (m_nLastIndex == 0)
        return;

    m_arData[1] = m_arData[m_nLastIndex];
    m_nLastIndex--;

    int nCurrent = 1;
    int nLeft = nCurrent * 2;
    int nRight = nLeft + 1;
    int nMin{};

    while (nRight <= m_nLastIndex) // 둘다 있는 경우
    {
        nMin = nLeft;
        if (m_arData[nLeft] > m_arData[nRight])
            nMin = nRight;

        if (m_arData[nCurrent] > m_arData[nMin])
            swap(m_arData[nCurrent], m_arData[nMin]);

        nCurrent = nMin;
        nLeft = nCurrent * 2;
        nRight = nLeft + 1;
    }
    if (nLeft == m_nLastIndex) // 왼쪽만 있는 경우 체크
    {
        if (m_arData[nCurrent] > m_arData[m_nLastIndex])
            swap(m_arData[nCurrent], m_arData[m_nLastIndex]);
    }


    //while (nLeft <= m_nLastIndex) // 간략화
    //{
    //    nMin = nLeft;
    //    if (nRight <= m_nLastIndex && m_arData[nLeft] > m_arData[nRight])
    //        nMin = nRight;

    //    if (m_arData[nCurrent] > m_arData[nMin])
    //        swap(m_arData[nCurrent], m_arData[nMin]);

    //    nCurrent = nMin;
    //    nLeft = nCurrent * 2;
    //    nRight = nLeft + 1;
    //}



}

void C_HEAP::print()
{
    for (int i = 1; i <= m_nLastIndex; i++)
    {
        printf("%d ", m_arData[i]);
    }
    printf("\n");
}

 

2. HEAP 알고리즘 재귀 함수

#include "heap.h"

void C_HEAP::swap(int& nDst, int& nSrc)
{
    int nTmp = nDst;
    nDst = nSrc;
    nSrc = nTmp;
}

void C_HEAP::up(int nCurrent, int nParent)
{
    if (nParent == 0 || m_arData[nCurrent] >= m_arData[nParent])
        return;

    swap(m_arData[nCurrent], m_arData[nParent]);
    up(nParent, nParent / 2);
}

bool C_HEAP::add(const int& nData)
{
    if (m_nLastIndex + 1 == 11)
        return false;

    m_nLastIndex++;
    m_arData[m_nLastIndex] = nData;

    up(m_nLastIndex, m_nLastIndex / 2);

    return true;
}

bool C_HEAP::top(int& nData)
{
    if (m_arData[m_nLastIndex = 0])
        return false;

    nData = m_arData[1];
    return true;
}

void C_HEAP::down(int nCurrent)
{
    int nChild = nCurrent * 2;

    if (nChild > m_nLastIndex)
        return;

    if (nChild + 1 <= m_nLastIndex && m_arData[nChild] > m_arData[nChild + 1])
        nChild++;

    if (m_arData[nCurrent] <= m_arData[nChild])
        return;

    swap(m_arData[nCurrent], m_arData[nChild]);
    down(nChild);
}

void C_HEAP::pop()
{
    if (m_nLastIndex == 0)
        return;

    m_arData[1] = m_arData[m_nLastIndex];
    m_nLastIndex--;

    down(1);
}

void C_HEAP::print()
{
    for (int i = 1; i <= m_nLastIndex; i++)
    {
        printf("%d ", m_arData[i]);
    }
    printf("\n");
}

3. Quick Sort

[ 강사님 코드 ]

#include <iostream>

void swap(int& nDst, int& nSrc);
void printData(const int* pData, int nLength);

int main()
{
	int arData[9]{ 6,8,7,1,9,3,2,5,4 };
	int arData[2] = {1,2};
	int arData[2] = {2,1};

	int* pData = arData;
	int nLength = 9;
	int nL = 1;
	int nR = nLength - 1;

	while (nL < nR)
	{
		while (pData[nL] < pData[0])
		{
			nL++;
		}
		while (pData[nR] > pData[0])
		{
			nR--;
		}
		if (nL < nR)
			swap(pData[nL], pData[nR]);
		else
			swap(pData[0], pData[nR]);
	}
	printData(pData, nLength);
}

void swap(int& nDst, int& nSrc)
{
    int nTmp = nDst;
    nDst = nSrc;
    nSrc = nTmp;
}

void printData(const int* pData, int nLength)
{
    for (int i = 0; i < nLength; i++)
    {
        printf("%d ", pData[i]);
    }
    printf("\n");
}

 

[ 내가 짠 코드 ] 

[ 내가 한거 ]
#include <iostream>

void swap(int& nDst, int& nSrc);
void printData(const int* pData, int nLength);


int main()
{
	int arData[9]{ 6,8,7,1,9,3,2,5,4 };

	int* pData = arData;
	int nLength = 9;
	int nL = 1;
	int nR = nLength - 1;

	while (nL != nR)
	{
		if (pData[nL] <= pData[0])
			nL++;
		if (pData[nR] >= pData[0])
			nR--;

		swap(pData[nL], pData[nR]);
		printData(pData, nLength);
	}
	swap(pData[nL], pData[0]);
	printData(pData, nLength);
}

void swap(int& nDst, int& nSrc)
{
    int nTmp = nDst;
    nDst = nSrc;
    nSrc = nTmp;
}

void printData(const int* pData, int nLength)
{
    for (int i = 0; i < nLength; i++)
    {
        printf("%d ", pData[i]);
    }
    printf("\n");
}