Как вывести отсортированный массив c

Update for debugging print

int* ar; // ** Указатель на int void quickSort(int a[], long N) < cout for (int k = 0; k < N; k++) cout > 1]; while (i < j) < while (a[i] < p) i++; while (a[j] >p) j--; if (i < j) swap(a[i++], a[j--]); >cout int main() < int a[10] = < 5,2,1,9,1,4,6,2,10 >; ar = a; // ** Установить указатель на первый элемент массива int N = 9; quickSort(a, N); funcprint(a, N); > 

Я исправил N из вашего кода на 9 (может и еще какие-то мелкие правки внес)

avp@avp-desktop:~/avp/hashcode$ g++ ttt.cpp -g avp@avp-desktop:~/avp/hashcode$ ./a.out N=9 5 2 1 9 1 4 6 2 10 ; p=1 j=1 i=2 1: 1 1 ; 2: 2 9 5 4 6 2 10 ; 1 1 2 9 5 4 6 2 10 N=1 N=7 2 9 5 4 6 2 10 ; p=4 j=2 i=3 1: 2 2 4 ; 2: 5 6 9 10 ; 1 1 2 2 4 5 6 9 10 N=2 2 2 ; p=2 j=0 i=1 1: 2 ; 2: 2 ; 1 1 2 2 4 5 6 9 10 N=0 N=1 N=4 5 6 9 10 ; p=9 j=2 i=2 1: 5 6 9 ; 2: 9 10 ; 1 1 2 2 4 5 6 9 10 N=2 5 6 ; p=6 j=1 i=1 1: 5 6 ; 2: 6 ; 1 1 2 2 4 5 6 9 10 N=1 N=1 N=2 9 10 ; p=10 j=1 i=1 1: 9 10 ; 2: 10 ; 1 1 2 2 4 5 6 9 10 N=1 N=1 1 1 2 2 4 5 6 9 10 avp@avp-desktop:~/avp/hashcode$ 

Кстати, интересно что уже после третьего вызова массив оказывается отсортированным, но алгоритму требуется сделать еще 10 вызовов, чтобы установить этот факт.

Вывод отсортированного массива 2-мя методами сортировки

Пишу на Ideone, задание состояло в сортировке массива 2-мя способами, в моем случае выбором и обменом, выводит как бы без ошибок, но сами массивы выводятся не отсортированными(должен выводится отсортированный, но выводится не отсортированный)

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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

#include int SortOtbor(int[], int);// функции сортировка выбором int SortObmen(int[], int);// функции сортировка обменом using namespace std; int main() { int V; cout"Введите номер варианта"endl; cin>>V; int size = 50+2*V; //размер массива int array[size] = {}; int array2[size]={};//создаем еще один массив, чтобы обе функции использовали один и тот же массив //заполним массивы случайными числами от 1 до 100 srand(time(NULL)); for(int i = 0; i  size; i++) { array[i] = 1 + rand() % 100; array2[i] = array[i];//копируем значения первого массива во второй, чтобы использовать его в другой функции } //выводим неотсортированный массив на экран cout  "Неотсортированный массив: "  endl; for (int i = 0; i  size; i++) cout array[i]" "; cout  endl  endl; //выводим отсортированный массив (выбором) на экран cout  "Отсортированный массив (выбором): "  endl; for (int i = 0; i  size; i++) cout array[i]" "; cout  endl  endl; //выводим отсортированный массив (обмена) на экран cout  "Отсортированный массив (обменом): "  endl; for (int i = 0; i  size; i++) cout array2[i]" "; cout  endl  endl; return 0; } /////////////////////////////////////////////////////////////////////////// int SortOtbor(int array[], int size) { int temp; for(int i = 0; i  size; ++i) // i - номер текущего шага { int pos = i; temp = array[i]; for(int j = i + 1; j  size; ++j) // цикл выбора наименьшего элемента { if (array[j]  temp) { pos = j; temp = array[j]; } } array[pos] = array[i]; array[i] = temp; // меняем местами наименьший с a[i] } } ////////////////////////////////////////////////////////////////////////// int SortObmen(int array2[], int size) { int temp; for(int i = 0; i  size - 1; ++i) // i - номер прохода { for(int j = 0; j  size - 1; ++j) // внутренний цикл прохода { if (array2[j + 1]  array2[j]) { temp = array2[j + 1]; array2[j + 1] = array2[j]; array2[j] = temp; } } } }

Добавлено через 18 часов 18 минут
Я дэлбич, уже выводит отсортированный массив 2-мя способами, но не считает количество обменов и перестановок(выводит просто "0"), объявлял их как глобальные, но и это тоже не помогает, можно ли решить проблему не прибегая к указателям?

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 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

#include #include int SortVibor(int[], int,int,int); int SortObmen(int[], int,int,int); using namespace std; int main() { int V; cout"Введите номер варианта"endl; cin>>V; int size = 50+2*V; //размер массива int array[size] = {}; int array2[size]= {};//создаем еще один массив, чтобы обе функции использовали один и тот же массив //заполним массивы случайными числами от 1 до 100 srand(time(NULL)); for(int i = 0; i  size; i++) { array[i] = 1 + rand() % 100; array2[i] = array[i];//копируем значения первого массива во второй, чтобы использовать его в другой функции } //выводим неотсортированный массив на экран cout  "Неотсортированный массив: "  endl; for (int i = 0; i  size; i++) { cout array[i]" "; } cout  endl  endl; /////////////////////////////////////////////////выводим отсортированный массив (выбором) на экран int count_2compare=0; int count_2switch = 0; SortVibor(array,size,count_2compare,count_2switch); cout  "Отсортированный массив (выбором): "  endl; for (int i = 0; i  size; i++) { cout array[i]" "; } coutendl; cout"Количество сравнений"" "count_2compareendl; cout"Количество обменов"" "count_2switchendl;; cout  endl  endl; ///////////////////////////////////////////////выводим отсортированный массив (обмена) на экран int count_compare = 0; int count_switch = 0; SortObmen(array2,size,count_compare,count_switch); cout  "Отсортированный массив (обменом): "  endl; for (int i = 0; i  size; i++) { cout array2[i]" "; } coutendl; cout"Количество сравнений"" "count_compareendl; cout"Количество обменов"" "count_switchendl;; cout  endl  endl; return 0; } ///////////////////////////////////////////////////////////////////////////////////////// int SortVibor(int array[], int size,int count_2compare,int count_2switch) { int min; for(int i = 0; i  size; ++i) // i - номер текущего шага { int pos = i; min = array[i]; count_2compare+=1; for(int j = i + 1; j  size; ++j) // цикл выбора наименьшего элемента { if (array[j]  min) { pos = j; min = array[j]; count_2switch+=1; } count_2compare+=1; } array[pos] = array[i]; array[i] = min; // меняем местами наименьший с array[i] } } //////////////////////////////////////////////////////////////////////////////////////// int SortObmen(int array2[], int size, int count_compare,int count_switch) { int temp; for(int i = 0; i  size - 1; ++i) // i - номер прохода { count_compare+=1; for(int j = 0; j  size - 1; ++j) // внутренний цикл прохода { if (array2[j + 1]  array2[j]) { temp = array2[j + 1]; array2[j + 1] = array2[j]; array2[j] = temp; count_switch+=1; } count_compare+=1; } } }

Как вывести отсортированный массив c

Оранжевым отмечаются элементы, которые нужно поменять местами. Зеленые уже стоят в нужном порядке.

Наибольший элемент — число 48 — оказался в конце списка.

Наибольший элемент уже занимает место в конце массива. Чтобы поставить следующее число по убыванию, можно пройтись лишь до 4-й позиции, а не пятой.

После четвертого прохода получаем отсортированный массив.

Функция сортировки в качестве параметров будет принимать указатель на массив и его размер. Функцией swap() элементы меняются местами друг с другом:

Зеленым отмечается наименьший элемент в подмассиве — он ставится в начало списка.

Число 4 — наименьшее в оставшейся части массива. Перемещаем четверку на вторую позицию после числа 0.

Напишем функцию поиска наименьшего элемента и используем ее в сортировке:

Число 12 больше 5 — элементы меняются местами.

Проход №2. Начинаем с третьей позиции.

Проверяем вторую и третью позиции. Затем первую и вторую.

Проход №3. Начинаем с четвертой позиции.

Произошло три смены местами.

Проход №4. Начинаем с последней позиции.

Получаем отсортированный массив на выходе.

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

Опорным может быть любой элемент. Мы выбираем последний в списке.

Чтобы расположить элементы большие — справа от опорного элемента, а меньшие — слева, будем двигаться от начала списка. Если число будет больше опорного, то оно ставится на его место, а сам опорный на место перед ним.

Напишем функцию разделения partition() , которая возвращает индекс опорного элемента, и используем ее в сортировке.

Цикл деления повторяется, пока не останется по одному элементу в массиве. Затем объединяем, пока не образуем полный список.

Алгоритм сортировки состоит из четырех этапов:

1. Найти середину массива.
2. Сортировать массив от начала до середины.
3. Сортировать массив от середины до конца.
4. Объединить массив.

Уменьшаем шаг в два раза. Шаг равен 2.

Индекс с нижним левым узлом определим по формуле n/2-1 , где n – длина массива. Получается 5/2 – 1 = 2 – 1 = 1 . С этого индекса и начинаем операцию heapify() . Сравним дочерние узлы 1-й позиции.

Дочерний узел оказался больше. Меняем местами с родителем.

Теперь проверяем родительский узел от позиции 1.

48 больше 3. Меняем местами.

После смены проверяем все дочерние узлы элемента, который опустили. То есть для числа 3 проводим heapify() . Так как 3 меньше 19, меняем местами.

Наибольший элемент оказался наверху кучи. Осталось поставить его в конце массива на позицию 4.

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

Повторяем алгоритм сортировки, пока куча не опустеет, и получаем отсортированный массив.

heapify.cpp

void heapify(int list[], int listLength, int root) < int largest = root; int l = 2*root + 1; int r = 2*root + 2; if (l < listLength && list[l] >list[largest]) largest = l; if (r < listLength && list[r] >list[largest]) largest = r; if (largest != root) < swap(list[root], list[largest]); heapify(list, listLength, largest); >> 

#include using namespace std; void heapify(int list[], int listLength, int root) < int largest = root; int l = 2*root + 1; int r = 2*root + 2; if (l < listLength && list[l] >list[largest]) largest = l; if (r < listLength && list[r] >list[largest]) largest = r; if (largest != root) < swap(list[root], list[largest]); heapify(list, listLength, largest); >> void heapSort(int list[], int listLength) < for(int i = listLength / 2 - 1; i >= 0; i--) heapify(list, listLength, i); for(int i = listLength - 1; i >= 0; i--) < swap(list[0], list[i]); heapify(list, i, 0); >> int main() < int list[5] = ; cout

Сложность алгоритма в любом случае: O(n*logn).

В этой статье мы познакомились с семью видами сортировок, рассмотрели их выполнение и написание на С++. Попробуйте применить новые знания в решении задачек на LeetCode или Codeforces . Понимание подобных алгоритмов поможет в будущем пройти собеседование.

• https://www.softwaretestinghelp.com/sorting-techniques-in-cpp/
• https://medium.com/@ssbothwell/sorting-algorithms-and-big-o-analysis-332ce7b8e3a1
• https://www.programiz.com/dsa/shell-sort
• https://www.happycoders.eu/algorithms/sorting-algorithms/

Материалы по теме

• Какая сортировка самая быстрая? Тестируем алгоритмы
• Пузырьковая сортировка на JavaScript
• Вводный курс по алгоритмам: от сортировок до машины Тьюринга

Мне сложно разобраться самостоятельно, что делать?

Алгоритмы и структуры данных действительно непростая тема для самостоятельного изучения: не у кого спросить и что-то уточнить. Поэтому мы запустили курс «Алгоритмы и структуры данных», на котором в формате еженедельных вебинаров вы:

• изучите сленг, на котором говорят все разработчики независимо от языка программирования: язык алгоритмов и структур данных;
• научитесь применять алгоритмы и структуры данных при разработке программ;
• подготовитесь к техническому собеседованию и продвинутой разработке.

Курс подходит как junior, так и middle-разработчикам.

Как вывести отсортированый массив?

Задача: Написать программу, которая вводит с клавиатуры 5 чисел и выводит их в возрастающем порядке.

Пример ввода:
3
2
15
6
17

Пример вывода:
2
3
6
15
17

Требования:
Программа должна считывать 5 чисел с клавиатуры.
Программа должна выводить 5 чисел, каждое с новой строки.
Выведенные числа должны быть отсортированы по возрастанию.
Вывод должен содержать те же числа, что и были введены (порядок не важен).
Solution.java

• Solution.java

Комментарии (13)

• популярные
• новые
• старые

Для того, чтобы оставить комментарий Вы должны авторизоваться
Уровень 40
12 января 2021, 19:22

Окромя того, о чём уже написали, выводить массив лучше потом, в отдельном цикле когда он уже будет весь отсортирован

Уровень 19
12 января 2021, 18:51

Мне больше нравится вариант с использованием Collections.sort(numbers); где numbers - это твой ArrayList который ты заполнил с клавиатууры. После этого простым перебором выводишь в консоль for (int number : numbers) < System.out.println(number); >

Уровень 19
12 января 2021, 18:52
Хотя да, идея в том, чтоб использовать массив.
kavasak119999 Backend Developer
12 января 2021, 16:57

У тебя 5 символов, а ты указал 6. Числа начинаются с 0. Ты же в цикле сортируешь массив, зачем выводить элементы во время сортировки? На выходе у тебя будет готовый массив, вот его и выводи

Уровень 20
12 января 2021, 17:46
Мне нужно вывести отсортированый масив, и это не получается.
Уровень 40
12 января 2021, 16:50

int [] mas = ; это строка создает массив, размер которого = 1 и значение mas[0] = Integer.parseInt(reader.readLine()

Уровень 40
12 января 2021, 16:55
20 строка бросит исключение java.lang.ArrayIndexOutOfBoundsException: 1
Уровень 20
12 января 2021, 17:50

Попытался переделать . Но теперь выводит только три числа из пяти , и компилятор показывает ошибкую Когда выношу System. в цыкл фор или ваил ,компилятор показывает только ошибку , без каких либо чисел. BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int a = Integer.parseInt(reader.readLine()); int b = Integer.parseInt(reader.readLine()); int c = Integer.parseInt(reader.readLine()); int d = Integer.parseInt(reader.readLine()); int f = Integer.parseInt(reader.readLine()); int [] mas = ; boolean isSorted = false; int buf; while (!isSorted) < isSorted = true; for (int i = 1 ; i < 5;i++)< if (mas[i] >mas[i+1]) < isSorted = false; buf = mas[i]; mas[i] = mas[i+1]; mas[i+1] = buf; System.out.println(mas[i]); >> >

Уровень 40
12 января 2021, 18:00

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); int a = Integer.parseInt(reader.readLine()); int b = Integer.parseInt(reader.readLine()); int c = Integer.parseInt(reader.readLine()); int d = Integer.parseInt(reader.readLine()); int f = Integer.parseInt(reader.readLine()); int [] mas = ; boolean isSorted = false; int buf; while (!isSorted) < isSorted = true; for (int i = 1 ; i < 5;i++)< //тут вы начинаете цикл с 1 , надо с нуля if (mas[i] >mas[i+1]) < // здесь когда i будет равно 4 вы обращаетесь к mas[i+1] значит к 5 элементу массива и выходите за границу isSorted = false; buf = mas[i]; mas[i] = mas[i+1]; mas[i+1] = buf; System.out.println(mas[i]); >> >

Уровень 40
12 января 2021, 18:02
у вас массив состоит из 5 элементов. (0,1,2,3,4) - индексы
kavasak119999 Backend Developer
12 января 2021, 18:04

Ты читал мой комментарий? У тебя цикл while(!isSorted) Сортирует массив, Меняет элементы местами! После полного прохода этого цикла, ты можешь создать новый цикл, и вывести все элементы

Уровень 40
12 января 2021, 18:10
Программа сломается 20 строке
kavasak119999 Backend Developer
12 января 2021, 18:12
я уже написал об этом выше, зачем повторяться

• Курсы программирования
• Регистрация
• Курс Java
• Помощь по задачам
• Цены
• Задачи-игры

Сообщество

JavaRush — это интерактивный онлайн-курс по изучению Java-программирования c нуля. Он содержит 1200 практических задач с проверкой решения в один клик, необходимый минимум теории по основам Java и мотивирующие фишки, которые помогут пройти курс до конца: игры, опросы, интересные проекты и статьи об эффективном обучении и карьере Java‑девелопера.