Одномерный массив. Пузырьковая сортировка.

Опубликовано 28.06.2012 | Автор: admin

Пузырьковая сортировка — это самая простая для человеческого восприятия сортировка, но очень неэффективная с точки зрения быстродействия. Тем не менее, в самом начале своего пути вы просто обязаны познакомиться с пузырьковой сортировкой.

Сортировка — это процесс перестановки чего-либо по какому-то признаку. Например, фамилии можно отсортировать по алфавиту, группу чисел по возрастанию или убыванию, учеников какой-то группы по успеваемости.

Под сортировкой массива понимают перестановку элементов массива любым заранее оговорённым образом: или по возрастанию/убыванию, или же с левой стороны массива положительные числа, идущие по возрастанию, а с правой отрицательные числа, идущие по возрастанию и т. п.

Начинается знакомство с сортировками с самых простых сортировок, при этом элементы, как правило, сортируются по убыванию или по возрастанию. В этой теме будет приведён пример сортировки массива по возрастанию.

Чтобы приступить к сортировке обычного массива, вы должны как минимум уметь менять переменные:

int a = 10;
int b = 100;
//Здесь вы пишете код
cout << a << '\n'; //на выходе должно получиться 100
cout << b << '\n'; //на выходе должно получиться 10

int a = 10;

int b = 100;

//Здесь вы пишете код

cout << a << '\n'; //на выходе должно получиться 100

cout << b << '\n'; //на выходе должно получиться 10

Нужно уметь не просто присваивать значения, а уметь взаимодействовать с уже существующими значениями переменных. Обычно создаётся временная переменная, которую используют как резерв для хранения значений. Эту маленькую задачу вам на самостоятельный разбор. Просто добавьте ещё одну переменную и заставьте её взаимодействовать с существующими: сначала нужно сохранить в резерве существующее значение, потом вытащить из резерва сохранённое значение.

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

Основа пузырьковой сортировки — сдвиг правильного элемента в край массива:

//Borland C++ 3.1   Основа пузырьковой сортировки   (Неготовый код)
#include <iostream.h>
#include <conio.h>

int main () {
clrscr();
    const int N = 9;
  int arr[N] = {9,8,7,2,5,4,3,6,1}; //Для краткости кода
  int temp;

  for (int i = 0; i < N-1; i++){
    if (arr[i] > arr[i+1]){
       temp = arr[i];       //Перестановка
       arr[i] = arr[i+1];
       arr[i+1] = temp;
    }
  }

  for (int i = 0; i<N; i++) cout << arr[i] << ' ';
  cin.get();
}

//Borland C++ 3.1 Основа пузырьковой сортировки (Неготовый код)

#include <iostream.h>

#include <conio.h>

int main () {

clrscr();

const int N = 9;

int arr[N] = {9,8,7,2,5,4,3,6,1}; //Для краткости кода

int temp;

for (int i = 0; i < N-1; i++){

if (arr[i] > arr[i+1]){

temp = arr[i]; //Перестановка

arr[i] = arr[i+1];

arr[i+1] = temp;

}

for (int i = 0; i<N; i++) cout << arr[i] << ' ';

cin.get();

}

Смысл показанного кода в том, чтобы вы поняли основу движения в пузырьковой сортировке. Если анализировать массив слева-направо (что я и делаю), то самый левый элемент постепенно впрыгивая вправо по ячейкам сдвигается в правильную для себя позицию, в правый край. Прыжки происходят, когда условием сравнения определяется, что элемент находится не на своём месте.

Более полный код пузырьковой сортировки:

//Borland C++ 3.1       Пузырьковая сортировка
#include <iostream.h>
#include <conio.h>

int main () {
    const int N = 9;
    int arr[N] = {9,8,7,2,5,4,3,6,1}; //Для краткости кода

  int temp;

  cout << "original: \t";
  for (int i = 0; i<N; i++) cout << arr[i] << ' ';
  cout << '\n';

  for (int i = 0; i < N-1; i++){    //Сужение массива путём смещения точки старта анализа
    for (int j = i+1; j < N; j++)   //Сдвиг некоторого элемента в край
    {
        if (arr[i] > arr[j]) {
            temp = arr[i];      //Смена мест
            arr[i] = arr[j];
            arr[j] = temp;
        };
    }
  }

  cout << "sorted: \t";
  for (int i = 0; i<N; i++) cout << arr[i] << ' ';
  cin.get();
}

//Borland C++ 3.1 Пузырьковая сортировка

#include <iostream.h>

#include <conio.h>

int main () {

const int N = 9;

int arr[N] = {9,8,7,2,5,4,3,6,1}; //Для краткости кода

int temp;

cout << "original: \t";

for (int i = 0; i<N; i++) cout << arr[i] << ' ';

cout << '\n';

for (int i = 0; i < N-1; i++){ //Сужение массива путём смещения точки старта анализа

for (int j = i+1; j < N; j++) //Сдвиг некоторого элемента в край

{

if (arr[i] > arr[j]) {

temp = arr[i]; //Смена мест

arr[i] = arr[j];

arr[j] = temp;

};

}

cout << "sorted: \t";

for (int i = 0; i<N; i++) cout << arr[i] << ' ';

cin.get();

}

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

Особенно внимательным надо быть к границам массива. Поскольку в моём коде процесс происходит слева-направо, а элемент сравнивается с правостоящим, то при обходе массива нужно бежать к предпоследнему элементу, а не последнему. Последний элемент учтётся как правостоящий, в противном случае последний элемент массива будет сравнен с элементом, стоящим за пределами массива, а в этом ничего хорошего нет. При сдвиге некоторого элемента в край переменная j обозначает правостоящий элемент. Поскольку изначально она непосредственный сосед, то она при каждом новом проходе (после вставки некоторого элемента в свой край) принимает значение i+1, потом она становится вторым соседом, третьим соседом и т. д. Поскольку она правый сосед, то её учитывать надо вместе с последним элементом массива.

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

Рубрика: Базовые знания, level "HelloWorld", Массивы

Just Learn:

02.01.2018 в 6:50 пп

Зачем в цикле написано N-1?

Ответить

admin:

02.01.2018 в 7:06 пп

Потому что N+1 (который по факту получается во вложенном цикле из-за начала не в нуле, а единице) будет учтён. Если не отнимать эту самую единицу, то мы вылезем ровно на 1 элемент за границу массива.
1 2 3
Сравниваются 1/2, 2/3; Чтобы закончить на двойке, мы (в показанном в примере случае) останавливаемся не на N, а на N-1, иначе (при остановке во внешнем цикле на N) выходит, что надо сравнить тройку с чем-то неизвестным, находящимся вне массива, за тройкой.
Вот как-то так.

2

Ответить

андрей:

10.02.2018 в 7:38 пп

void __fastcall TForm1::N14Click(TObject *Sender)
{
AnsiString a;
for (int k=1;k<StringGrid1->RowCount; k++)
for (int i=1;i<StringGrid1->RowCount-k; i++)
if (StrToInt(StringGrid1->Cells[1][i])>StrToInt(StringGrid1->Cells[1][i+1]))
for (int j=1; j<=StringGrid1->ColCount;j++)
{a=StringGrid1->Cells[j][i+1];
StringGrid1->Cells[j][i+1]=StringGrid1->Cells[j][i];
StringGrid1->Cells[j][i]=a;
}
}

как тут сделать чтобы сортировка была от буквы А до Я, мне нужно сделать так чтобы ФИО преподавателей сортировалось методом омена

Одномерный массив. Пузырьковая сортировка.

3 комментария на «“Одномерный массив. Пузырьковая сортировка.”»

Добавить комментарий Отменить ответ

Поиск

Последние темы

Случайная книга в электронном формате

Последние комментарии

Мета