[С++] Лаба по массивам

[natashasuper5]

Задание
Осуществить поиск элемента в массиве. Отсортировать массив, используя Быстрая сортировка!!!!!

Указания
Элементы массивов задаются пользователем с клавиатуры. На монитор должен выводиться индекс найденного в массиве элемента. На экран выводится исходное состояние массива, и транслируются все изменения, происходящие в массиве во время сортировки.

Ход работы
1. Ознакомиться с теоретическим материалом;
2. Определить массив, состоящий из 50 элементов;
3. Проинициализировать массив данными вводимыми с клавиатуры;
4. Вывести значения элементов массива последовательно на экран;
5. Найти в массиве значение введённое с клавиатуры;
6. Отсортировать массив, используя алгоритм быстрой сортировки, при этом во время сортировки на экран выводятся текущие состояния массива;
7. Вывести на экран значения итогового массива с пояснением;





вот теория на всякий случай:



Основная идея быстрой сортировки напоминает метод поиска делением пополам. Сначала выбирается средний элемент в сортируемом массиве. Все, что больше этого элемента переносится в правую часть массива, а все, что меньше – в левую. После первого шага средний элемент оказывается на своем месте. Затем аналогичная процедура повторяется для каждой половины массива. На каждом последующем шаге размер обрабатываемого фрагмента массива уменьшается вдвое. Количество операций, которое требуется для реализации этой процедуры, оценивается константой n*log2n. Это еще быстрее, чем сортировка Шелла. В отличие от предыдущих функций быстрая сортировка оформлена из двух функций – quick, которая допускает принятое в других функциях обращение, и рекурсивной процедуры qs:

void quick(int *x, int n)
{ qs(x,0,n-1); }
//----------------------------------
void qs(int *x,int left,int right)
{ register int i,j;
  int xx,tmp;
  i=left; j=right;
  xx=x[(left+right)/2];
  do { while(x[i]<xx && i<right)i++;
       while(xx<x[j] && j>left) j--;
       if(i<=j)
         { tmp=x[i]; x[i]=x[j];
           x[j]=tmp; i++; j--;
         }
      }
   while(i<=j);
   if(left<j) qs(x,left,j);
   if(i<right)qs(x,i,right);
}
Головная программа, предназначенная для тестирования и хронометража функций сортировки, приведена ниже. Заложенная в ней константа MAX для целей отладки принимает значение 20. Для хронометража методов сортировки ее надо увеличить до 100000 (BCB массивы такого размера допускает).
#include <iostream.h>
#include <conio.h>
#include <dos.h>
#define MAX 20
void bubble(int *x,int n);
void select(int *x,int n);
void insert(int *x,int n);
void shell(int *x,int n);
void quick(int *x,int n);
void qs(int *x,int left,int right);
void main()
{ int num[MAX],i;
  int t1,t2;
/* при отладке включить этот фрагмент
  cout << "Before sort:\n";
  for(i=0; i<MAX; i++)
    { num[i]=random(MAX);
      cout << num[i] << " ";
    }
  cout << endl;
*/
  t1=GetTickCount();
//  bubble(num,MAX);
//  select(num,MAX);
//  insert(num,MAX);
//  shell(num,MAX);
  quick(num,MAX);
  t2=GetTickCount();
  cout << t2-t1;
/* при отладке включить этот фрагмент
  cout << "After sort:" << endl;
  for(i=0; i<MAX; i++)
    cout << num[i] << " ";
  cout << endl;
*/
  cout << "end";
  getch();
}
//Методы сортировки
В таблице приведены данные работы каждой функции сортировки на массиве длиной в 100000 элементов на компьютере типа Pentium 4 (частота 2 ГГц). Сортируемый массив заполнялся случайными числами (для каждой функции набор исходных данных был одинаков).

Функция    Время сортировки в млсек
bubble    20312
insert    5266
select    10843
shell    1406
quick    16

[NiCola999]

ну неужели не понятно, что читать это невозможно. В тег CODE оберните свой код...