Даны числа A1, A2,..., An . Получить в порядке возрастания все различные числа, входящие в A1 ,A2 ,..., An.
Задача № 5 (Сортировка массивов) (см. "Сборник задач для начинающего программиста")
Алгоритм:
1. Описываем сортировку qsort:
quickSort ( массив a, верхняя граница N ) {
Выбрать опорный элемент p - середину массива
Разделить массив по этому элементу
Если подмассив слева от p содержит более одного элемента,
вызвать quickSort для него.
Если подмассив справа от p содержит более одного элемента,
вызвать quickSort для него.
}
2. Сортируем при помощи qsort исходный массив.
3. Выводим 1-ый эл-нт на экран.
4. Начиная со 2-го эл-та, проходимся по исходному массиву, и если текущий элемент не равен предыдущему, то выводим его на экран.
#include <iostream>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
void qSort(int*, int); // qSort
void printArr(int*, int); // Печать массива
int main() {
int a[80], N; // N -- последний элемент массива a[]
cout << "N="; cin >> N;
// Рандомно заполняем массив a[]
srand( time(NULL) );
for(int i=0; i<N; i++)
a[i]=rand() % 10;
printArr(a,N); // Выведем отрандоменый массив на экран
qSort(a, N); // Сортируем его
printArr(a,N); // Выводим отсортированный на экран
cout << a[0] << ' '; // Выводим первый элемент
for(int i=1; i<N; i++) { // Проходимся по массиву, начиная со 2-го элемента
if(a[i] != a[i-1]) // Если текущий эл-нт не равен предыдущему, то...
cout << a[i] << ' '; // ...выводим его на экран
}
cout << endl;
getch();
return 0;
}
// - - - - - - - - - - - -
// Быстрая сортировка (qSort)
void qSort(int* a, int N) {
// На входе - массив a[], a[N] - его последний элемент.
int i=0, j=N-1; // поставить указатели на исходные места
int temp, p;
p = a[ (N-1)>>1 ]; // центральный элемент
// процедура разделения
do {
while( a[i]<p ) i++;
while( a[j]>p ) j--;
if (i <= j) {
temp = a[i]; a[i] = a[j]; a[j] = temp;
i++; j--;
}
} while( i<=j );
// рекурсивные вызовы, если есть, что сортировать
if ( j > 0 ) qSort(a, j+1);
if ( (N-1) > i ) qSort(a+i, N-i);
}
// - - - - - - - - - - - - -
// Печать массива
void printArr(int* a, int N) {
int i;
for(i=0; i<N; i++) {
cout << a[i] << ' ';
}
cout << endl;
}