Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [С++] Лаба по массивам

Автор: natashasuper5 4.6.2010, 18:54

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

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

Ход работы
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

Автор: toxx 4.6.2010, 22:35

А что не выходит?

Автор: natashasuper5 4.6.2010, 22:41

я вообще не понимаю как делать это

Автор: toxx 4.6.2010, 22:53

не понятно, что нужно сделать
это(оно вроде у вас сделано)

Цитата

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

или это(тут просто define и тип изменить надо)

Цитата

значение 20. Для хронометража методов сортировки ее надо увеличить до 100000 (BCB массивы такого размера допускает).

Автор: natashasuper5 4.6.2010, 22:58

ну это вам всё понятно.а мне нет.и ничего там не сделано!то теория просто и к моему заданию не относится

Автор: toxx 4.6.2010, 23:03

измените, должно быть под вашу задачу

Код


#define MAX 100000
.....
unsigned long num[MAX]

И если уж у вас сортировка не верно сделана, вот верная

Код


void QuickSort(long* in,int a,int b)
{
     int i,j,mode;
     if(a>=b)return;
     for(i=a,j=b,mode=1;i<j;mode>0?j--:i++)
    {
        if(in[i]<in[j])
        {
        long t = in[j];
            in[j]=in[i];
            in[i]=t;
            mode=-mode;
        }
    }
    QuickSort(in,a,i-1);
    QuickSort(in,i+1,b);
}

Автор: natashasuper5 4.6.2010, 23:15

спасибо...только как то мало тут..вроде больше должно быть

Автор: toxx 4.6.2010, 23:21

natashasuper5
имеете ввиду функцию сортировки?За неё не беспокойтесь она рабочая