Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Antosha
0 / 0 / 0
Регистрация: 23.06.2014
Сообщений: 110
#1

Объяснить линейный поиск в массиве и сортировка массива - C++

18.08.2014, 22:32. Просмотров 1302. Ответов 3
Метки нет (Все метки)

Рябята кому не трудно кто может обяснить линейный поиск в масиве и сортировку масива

Не очень понял как на парах обясняли обясните вы пожалуйста буду благодарен!
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.08.2014, 22:32
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Объяснить линейный поиск в массиве и сортировка массива (C++):

Линейный поиск в массиве - C++
Подскажите пожалуйста ,что нужно сделать для реализации линейного поиска в данном массиве? Буду очень признателен. #include...

Линейный поиск в массиве и списке - C++
Добрый день, дорогие форумчане! Имеется программа, которая должна выполнять линейный поиск по ключу в массиве и списке, но функция поиска...

Линейный поиск в массиве структуры - C++
Нужно с помощью линейного поиска искать в готовом массиве структуры значение вводимое с клавиатуры. Напишите шаблон , по которому это можно...

Линейный поиск с барьером в массиве структур (С++) - C++
Здравствуйте! Помогите , пожалуйста , разобраться с поиском . Вот я создаю структуру : struct D //описываемая струтура { ...

Линейный поиск в числовом массиве с барьером и без барьера по числовому ключу - C++
Линейный поиск в числовом массиве с барьером и без барьера по числовому ключу. Не могу понять почему ругается на поиск с барьером....

Ближайшее число в массива (линейный поиск) - C++
Нужно найти ближайшее число в массиве. Собственно говоря мой код #include <iostream> using namespace std; int main(){ int x, y;...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
EfimKR
53 / 26 / 10
Регистрация: 24.06.2014
Сообщений: 229
Записей в блоге: 1
18.08.2014, 22:57 #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Линейный поиск - берём наш массив и перебираем всё элементы с 1 по последний, сравнивая с искомым значением.
C++
1
2
3
4
5
6
int i_find; // порядковый номер искомого элемента, если он найден.
int mas[SizeOfMas]; // заполнен каким-то образом
for (int i=0; i<SizeOfMas; i++)
{
    if(mas[i] == 17) i_find=i;
}
Добавлено через 3 минуты
"Пузырьковая" сортировка.
Идея метода состоит в следующем: шаг сортировки заключается в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. Для реализации расположим массив сверху вниз, от нулевого элемента - к последнему. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию.
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
Пример кода.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <typename T>
void bubbleSort(T a[], long size){
    long i, j;
    T x;
    for(i=0;i<size;i++){            // i - номер прохода
        for(j=size-1;j>i;j--){     // внутренний цикл прохода
            if(a[j-1]>a[j]){
                x=a[j-1];
                a[j-1]=a[j];
                a[j]=x;
            }
        }
    }
}
 
void main(){
    srand(time(NULL));
    const long SIZE=10;
    int ar[SIZE];
    
    // до сортировки
    for(int i=0;i<SIZE;i++){
        ar[i]=rand()%100;
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
    bubbleSort(ar,SIZE);
 
    // после сортировки
    for(int i=0;i<SIZE;i++){
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
}

Основные принципы метода.
Среднее число сравнений и обменов имеют квадратичный порядок роста, отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен. Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.

Рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла. Таким образом первый шаг оптимизации заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.

Процесс оптимизации можно продолжить, запоминая не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседних элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя "легкий" пузырек снизу поднимется наверх за один проход, "тяжелые" пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <typename T>
void shakerSort(T a[], long size) {
  long j, k=size-1;
  long lb=1, ub=size-1; // границы неотсортированной части массива
  T x;
 
  do{
      // проход снизу вверх 
    for(j=ub;j>0;j--){
        if(a[j-1]>a[j]){
            x=a[j-1];
            a[j-1]=a[j];
            a[j]=x;
            k=j;
        }
    }
    lb = k+1;
 
    // проход сверху вниз 
    for(j=1;j<=ub;j++){
        if(a[j-1]>a[j]){
            x=a[j-1];
            a[j-1]=a[j];
            a[j]=x;
            k=j;
        }
    }
    ub=k-1;
 
  }while (lb<ub);
}
 
void main(){
    srand(time(NULL));
    const long SIZE=10;
    int ar[SIZE];
    
    // до сортировки
    for(int i=0;i<SIZE;i++){
        ar[i]=rand()%100;
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
    shakerSort(ar,SIZE);
 
    // после сортировки
    for(int i=0;i<SIZE;i++){
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
}
Добавлено через 1 минуту
Сортировка выбором
Идея данного метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке.

Сейчас, мы с вами попробуем построить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1). На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.


Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] является упорядоченной. Таким образом, на шаге (n-1) вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево. Рассмотрим пример, реализующий данный метод:


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
template <typename T>
void selectSort(T a[], long size) {
    long i, j, k; 
    T x;
 
    for(i=0;i<size;i++) {       // i - номер текущего шага
        k=i;
        x=a[i];
 
        for(j=i+1;j<size;j++)   // цикл выбора наименьшего элемента
            if(a[j]<x){
                k=j;
                x=a[j];         // k - индекс наименьшего элемента
            }
        a[k]=a[i];
        a[i]=x;     // меняем местами наименьший с a[i]
    }
}
 
void main(){
    srand(time(NULL));
    const long SIZE=10;
    int ar[SIZE];
    
    // до сортировки
    for(int i=0;i<SIZE;i++){
        ar[i]=rand()%100;
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
    selectSort(ar,SIZE);
 
    // после сортировки
    for(int i=0;i<SIZE;i++){
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
}

Основные принципы метода
1. Для нахождения наименьшего элемента из n+1 рассматриваемых алгоритм совершает n сравнений. Таким образом, так как число обменов всегда будет меньше числа сравнений, время сортировки возрастает относительно количества элементов.

2. Алгоритм не использует дополнительной памяти: все операции происходят "на месте".

Давайте, определим, насколько устойчив данный метод? Рассмотрим последовательность из трех элементов, каждый из которых имеет два поля, а сортировка идет по первому из них. Результат ее сортировки можно увидеть уже после шага 0, так как больше обменов не будет. Порядок ключей 2a, 2b был изменен на 2b, 2a.


Таким образом, входная последовательность почти упорядочена, то сравнений будет столько же, значит алгоритм ведет себя не очень оптимально. Однако, такую сортировку можно использовать для массивов имеющих небольшие размеры.

Добавлено через 1 минуту
Сортировка вставками.
Сортировка простыми вставками в чем-то похожа на методы изложенные в предыдущих разделах урока. Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность.

Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы.

Будем разбирать алгоритм, рассматривая его действия на i-м шаге. Как говорилось выше, последовательность к этому моменту разделена на две части: готовую a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск подходящего места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется.


Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда найден элемент, меньший x или достигнуто начало последовательности.

Реализация метода
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <stdlib.h>
#include <time.h>
 
using namespace std;
 
template <typename T>
void insertSort(T a[], long size) {
    T x;
    long i, j;
 
    for(i=0;i<size;i++){  // цикл проходов, i - номер прохода
        x=a[i];
        
        // поиск места элемента в готовой последовательности 
        for (j=i-1;j>=0&&a[j]>x;j--)
                a[j+1]=a[j];    // сдвигаем элемент направо, пока не дошли
 
        // место найдено, вставить элемент
        a[j+1] = x;
    }
}
 
void main(){
    srand(time(NULL));
    const long SIZE=10;
    int ar[SIZE];
    
    // до сортировки
    for(int i=0;i<SIZE;i++){
        ar[i]=rand()%100;
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
    insertSort(ar,SIZE);
 
    // после сортировки
    for(int i=0;i<SIZE;i++){
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
}

Принципы метода
Хорошим показателем сортировки является весьма естественное поведение: почти отсортированный массив будет досортирован очень быстро. Это, вкупе с устойчивостью алгоритма, делает метод хорошим выбором в соответствующих ситуациях. Однако, алгоритм можно слегка улучшить. Заметим, что на каждом шаге внутреннего цикла проверяются 2 условия. Можно объединить из в одно, поставив в начало массива специальный "сторожевой элемент". Он должен быть заведомо меньше всех остальных элементов массива.


Тогда при j=0 будет заведомо верно a[0] <=x. Цикл остановится на нулевом элементе, что и было целью условия j>=0. Таким образом, сортировка будет происходить правильным образом, а во внутреннем цикле станет на одно сравнение меньше. Однако, отсортированный массив будет не полон, так как из него исчезло первое число. Для окончания сортировки это число следует вернуть назад, а затем вставить в отсортированную последовательность a[1]...a[n].



C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <stdlib.h>
#include <time.h>
 
using namespace std;
 
template <typename T>
void setMin(T a[],long size){
    T min=a[0];
    for(int i=1;i<size;i++)
        if(a[i]<min)
            min=a[i];
    a[0]=min;   
}
 
template <class T>
void insertSortGuarded(T a[], long size) {
    T x;
    long i, j;
    T backup = a[0];            // сохранить старый первый элемент
    setMin(a,size);             // заменить на минимальный
 
    // отсортировать массив
    for(i=1;i<size;i++){    
        x = a[i];
 
        for (j=i-1;a[j]>x;j--)
            a[j+1]=a[j];
 
        a[j+1] = x;
    }
 
    // вставить backup на правильное место
    for(j=1;j<size&&a[j]<backup;j++)
        a[j-1]=a[j];
 
    // вставка элемента 
    a[j-1] = backup;
}
 
void main(){
    srand(time(NULL));
    const long SIZE=10;
    int ar[SIZE];
    
    // до сортировки
    for(int i=0;i<SIZE;i++){
        ar[i]=rand()%100;
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
    insertSortGuarded(ar,SIZE);
 
    // после сортировки
    for(int i=0;i<SIZE;i++){
        cout<<ar[i]<<"\t";
    }
    cout<<"\n\n";
}
Antosha
0 / 0 / 0
Регистрация: 23.06.2014
Сообщений: 110
18.08.2014, 23:35  [ТС] #3
EfimKR, Спасибо большое
Тамика
Котовчанин
870 / 450 / 143
Регистрация: 16.02.2010
Сообщений: 2,961
Записей в блоге: 27
19.08.2014, 08:32 #4
Алгоритмы сортировок
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.08.2014, 08:32
Привет! Вот еще темы с ответами:

Сортировка и двоичный поиск в массиве. - C++
Помогите чайнику изменить следующий код: // F_08_L_2.cpp: определяет точку входа для консольного приложения. // #include...

Сортировка массива по возрастанию + поиск дубликатов - C++
Добрый день:) Я новичек:) подскажите плиз, почему когда помещаю в массив случайные числа, они потом с каждым новым запуском программы...

Обработка одномерного массива: поиск, перестановка, сортировка - C++
Для одномерного массива, состоящего из n вещественных чисел: а) найти максимальный элемент массива; б) вычислить сумму элементов с...

Блочная сортировка массива и поиск заданного элемента - C++
Помогите пожалуйста написать такую программу. Задание: Написать программу, которая реализует: 1. алгоритм блочной сортировки...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
19.08.2014, 08:32
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru