ITHouse

소스

#include <iostream>
using namespace std;

void exchange(int *arr, int x, int y) {
    int c = arr[x];
    arr[x] = arr[y];
    arr[y] = c;
}

class ATMarr {
private:
    int* m_pArr;
    int m_nVal;
public:
    ATMarr() {

    }
    ATMarr(int val) {
        m_nVal = val;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    ~ATMarr() {
        delete[] m_pArr;
    }
    void SetVal(){
        cin >> m_nVal;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    int GetVal() {
        return m_nVal;
    }
    void SetArr() {
        for (int i = 0; i < m_nVal; i++) {
            cin >> m_pArr[i];
        }
    }

    void printArr() {
        for (int i = 0; i < m_nVal; i++)
            cout << endl << m_pArr[i];
    }

    int Result() {
        int total = 0;
        for (int i = 0; i < m_nVal; i++) {
            total = m_pArr[i] * (m_nVal - i) + total;
        }
        return total;
    }
    void QuickSort(int low, int high) {
        int partitionVal=0;
        if (low < high) {
            partition(low, high, partitionVal);
            QuickSort(low, partitionVal - 1);
            QuickSort(partitionVal + 1, high);
        }
    }
    void partition(int low, int high, int &partitionVal) {
        int lastSmall=low;
        for (int i = low+1; i <= high; i++) {
            if (m_pArr[low] >=  m_pArr[i]) {
                ++lastSmall;
                exchange(m_pArr, i, lastSmall);
            }
        }
        partitionVal = lastSmall;
        exchange(m_pArr, partitionVal, low);
    }

};

int main()
{
    ATMarr ex;
    int val;
    ex.SetVal();
    ex.SetArr();
    val = ex.GetVal();
    ex.QuickSort(0, val-1);
    cout << ex.Result();

    return 0;
}

실수한점

quicksort를 이용하여 배열을 나열하려 하였다.

quicksort에서 
    void partition(int low, int high, int &partitionVal) {
        int lastSmall=low;
        for (int i = low+1; i <= high; i++) {
            if (m_pArr[low] >=  m_pArr[i]) {
                ++lastSmall;
                exchange(m_pArr, i, lastSmall);
            }
        }
        partitionVal = lastSmall;
        exchange(m_pArr, partitionVal, low);
    }

위의 파티션 부분에서 두번 틀렸었다.

1. if (m_pArr[low] >= m_pArr[i]) 이부분에서 >=이렇게 해야 같은 숫자가 나와도 lastSmall을 증가시켜 준다.

2.for (int i = low+1; i <= high; i++) 이렇게 해야 high까지 간다. 예를들어 배열이 5까지 인데 555 1 2 3 4 이렇게 되있을때 1 2 3 4 555 가 되고 그다음 회차에서 partitionVal은 4가 되고 QuickSort(low, partitionVal-1); QuickSort(partitionVal + 1, high); 이 부분에서 (0,3) (5,4) 이런식으로 되어 (0,3에서) 0,1,2만 파티션에서 실행된다.

추가적으로 안 사실

#include의 sort라는 함수가 있다.

#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int arr[5] = { 55,22,33,11,77 };
    sort(arr, arr + 5);
    for (int i = 0; i <= 4; i++) {
        cout << arr[i] << endl;
    }

}

위와같이 써서 quicksort대신 사용하여도 된다.

#include <iostream>
#include <algorithm>
using namespace std;

void exchange(int *arr, int x, int y) {
    int c = arr[x];
    arr[x] = arr[y];
    arr[y] = c;
}

class ATMarr {
private:
    int* m_pArr;
    int m_nVal;
public:
    ATMarr() {

    }
    ATMarr(int val) {
        m_nVal = val;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    ~ATMarr() {
        delete[] m_pArr;
    }
    void SetVal(){
        cin >> m_nVal;
        while (m_nVal < 1 && m_nVal>1000) {
            cin >> m_nVal;
        }
        m_pArr = new int[m_nVal];
    }
    int GetVal() {
        return m_nVal;
    }
    void SetArr() {
        for (int i = 0; i < m_nVal; i++) {
            cin >> m_pArr[i];
        }
    }

    void printArr() {
        for (int i = 0; i < m_nVal; i++)
            cout << endl << m_pArr[i];
    }

    int Result() {
        int total = 0;
        for (int i = 0; i < m_nVal; i++) {
            total = m_pArr[i] * (m_nVal - i) + total;
        }
        return total;
    }
    void QuickSort(int low, int high) {
        int partitionVal=0;
        if (low < high) {
            partition(low, high, partitionVal);
            QuickSort(low, partitionVal - 1);
            QuickSort(partitionVal + 1, high);
        }
    }
    void partition(int low, int high, int &partitionVal) {
        int lastSmall=low;
        for (int i = low+1; i <= high; i++) {
            if (m_pArr[low] >=  m_pArr[i]) {
                ++lastSmall;
                exchange(m_pArr, i, lastSmall);
            }
        }
        partitionVal = lastSmall;
        exchange(m_pArr, partitionVal, low);
    }
    void Sort() {
        sort(m_pArr, m_pArr + m_nVal);
    }

};

int main()
{
    ATMarr ex;
    int val;
    ex.SetVal();
    ex.SetArr();
    val = ex.GetVal();
    //ex.QuickSort(0, val-1);
    ex.Sort();
    cout << ex.Result();

    return 0;
}

결과