Вывод отсортированного массива 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++
В этом посте мы обсудим, как отсортировать массив в порядке возрастания в C++.
Чтобы отсортировать массив в естественном/возрастающем порядке, вы можете использовать std::sort алгоритм, предоставляемый STL. Он сортирует элементы контейнера в диапазоне, указанном указанными итераторами. Поскольку итераторы — это не что иное, как обобщение указателей, вы можете передать указатель на первый элемент массива и (1+) последний элемент массива для сортировки всего массива в стиле C.
int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ;
std :: sort ( arr , arr + n ) ;
for ( int const &i : arr ) <
std :: cout << i << ' ' ;
результат:
2 3 4 5 7
Стоит отметить, что std::sort не дает стабильной сортировки. Это означает, что относительный порядок одинаковых элементов не будет сохранен в отсортированной последовательности. Рекомендуемый подход к получению стабильной сортировки заключается в использовании std::stable_sort алгоритм.
Кроме того, приведенный выше код требует, чтобы вы заранее знали размер массива. Можно пропустить это в C++11 используя новые std::begin а также std::end функции, которые перегружены для массивов в стиле C:
почему не работает код и как вывести отсортированный массив?
В соответствии с algorithm quicksort Хоара из википедии, который, похоже, вы пытаетесь реализовать, функция, написанная на С++ с тем же прототипом, что и ваша, может выглядеть вот так:
void quickSort (int a[], long N) < if (N < 2) return; long i = 0, j = N - 1; int p = a[N >> 1]; while (i < j) < while (a[i] < p) i++; while (a[j] >p) j--; if (i < j) swap(a[i++], a[j--]); >quickSort(a, j); quickSort(a + i, N - i); > Замечу также, что перестановка элементов в соответствии с текстом алгоритма из википедии должна записываться именно так: if (i < j) swap(a[i++], a[j--]);
if (i
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 вызовов, чтобы установить этот факт.
Сортировка массива C#. Алгоритм «Сортировка выбором»
уважаемые посетители блога, если Вам понравилась, то, пожалуйста, помогите автору с лечением. Подробности тут.
На данный момент у нас уже хватает знаний, чтобы попробовать написать простейшую программу в C#. Но, простейшая — не значит бесполезная. Наша программа будет сортировать массив C#. При написании различных программ нам часто приходится сталкиваться с таким понятием как сортировка. Например, необходимо отсортировать список людей по алфавиту или произвести сортировку оценок учащихся по возрастанию. И для того, чтобы максимально эффективно решить такую задачу мы должны знать не только сам язык программирования, но и алгоритмы сортировки — их сложность, как они реализуются на практике и так далее. Сегодня мы рассмотрим самый простой алгоритм сортировки массива C# — сортировку выбором.
Задача
Пользователь вводит с клавиатуры целые числа, разделенные запятой. Программа должна собрать из этих чисел массив и отсортировать его по возрастанию.
В консоль программа выведет неотсортированный и отсортированный массивы.
Алгоритм «Сортировка выбором»
Этот алгоритм является одним из самых простейших алгоритмов сортировки массива. Его смысл заключается в том, чтобы, чтобы идти по массиву, например слева направо, каждый раз искать минимальный элемент массива и обменивать его с первым элементом неотсортированной части массива. Шаги алгоритма можно представить следующим образом:
- Находим минимальный элемент в массиве.
- Меняем местами минимальный и первый элемент местами.
- Ищем минимальный элемент в неотсортированной части массива, т.е., начиная уже со второго элемента массива.
- Меняем местами второй элемент массива и найденный минимальный.
- Ищем минимальный элемент в массиве, начиная с третьего, меняем местами третий и минимальный элементы.
- Продолжаем алгоритм до тех пор пока не дойдем то конца массива.
Реализация алгоритма сортировки выбором в C#
Вначале приведу реализацию алгоритма сортировки массивы выбором в C#. Код постарался максимально пояснить с помощью комментариев:
//intArray - это массив целых чисел int indx; //переменная для хранения индекса минимального элемента массива for (int i = 0; i < intArray.Length; i++) //проходим по массиву с начала и до конца < indx = i; //считаем, что минимальный элемент имеет текущий индекс for (int j = i; j < intArray.Length; j++) //ищем минимальный элемент в неотсортированной части < if (intArray[j] < intArray[indx]) < indx = j; //нашли в массиве число меньше, чем intArray[indx] - запоминаем его индекс в массиве >> if (intArray[indx] == intArray[i]) //если минимальный элемент равен текущему значению - ничего не меняем continue; //меняем местами минимальный элемент и первый в неотсортированной части int temp = intArray[i]; //временная переменная, чтобы не потерять значение intArray[i] intArray[i] = intArray[indx]; intArray[indx] = temp; >
Проверить работу алгоритма нам поможет небольшая консольная программка в C#, которую мы сейчас и напишем.
Программа сортировки массива C# выбором
По условию задачи пользователь может ввести любое количество целых чисел, разделенных запятыми. Нам необходимо прочитать эти числа, составить из полученных чисел массив, вывести его в консоль, отсортировать массив приведенным выше алгоритмом и вернуть в консоль отсортированный массив. Все эти шаги реализуются достаточно просто.
Собираем массив целых чисел
Console.WriteLine("Введите через запятую целые числа и нажмите Enter"); string[] nums = Console.ReadLine().Split(new char[] < ',' >); int[] intArray = new int[nums.Length]; for (int i = 0; i
В первой строке мы предлагаем пользователю ввести целые числа. После того, как пользователь введет любое количество чисел и нажмет Enter, программа переходит к следующему шагу — разделит полученную от пользователя строку на массив строк:
string[] nums = Console.ReadLine().Split(new char[] < ',' >);
Метод Console.ReadLine() возвращает нам последнюю строку из консоли.
Метод Split(new char[] < ',' >) — это метод для типа string , который возвращает массив строк, созданный из исходной строки. В качестве аргумента этот метод принимает массив символов по которым будет делиться строка. Так как у нас, по условиям задачи, разделитель всего один — запятая, то и массив разделителей в методе Split() содержит всего один элемент.
На следующем шаге мы создаем массив целых чисел размер которого совпадает с размером массива nums .
int[] intArray = new int[nums.Length]
Далее, в цикле for мы наполняем наш созданный массив числами, используя метод Parse() у типа данных int , который возвращает нам целое число из строки.
for (int i = 0; i
Выводим неотсортированный массив в консоль
Вывести неотсортированный массив пользователю проще простого, если воспользоваться циклом foreach :
Console.WriteLine("Неотсортированный массив:"); foreach (int value in intArray) < Console.Write($""); >
Сортируем массив, используя алгоритм «Сортировка выбором» и показываем результат
Для этого используем реализацию алгоритма, которая представленная выше. Чтобы вывести отсортированный массив пользователю снова используем цикл foreach .
Console.WriteLine("\r\nОтсортированный массив:"); foreach (int value in intArray) < Console.Write($""); >
так как для неосортированного массива мы использовали метод Console.Write() , которые не производит переход на следующую строку, то здесь, в методе Console.WriteLine() мы использовали управляющие символы C# /r/n для перехода на новую строку и возврат каретки в начало строки.
Результат работы программы
В результате работы программы можно получить, например, вот такой вывод в консоли:
Введите через запятую целые числа и нажмите Enter
Неотсортированный массив: 0 100 999 345 -100 1 0 9 7 6 5 4 3 2 1 67 88
Отсортированный массив: -100 0 0 1 1 2 3 4 5 6 7 9 67 88 100 345 999
Как видите, алгоритм успешно справляется с сортировкой массива и все заданные числа были отсортированы от меньшего к большему.
Исходный код программы
Ниже приведен весь исходный код программы C# для сортировки массива:
using System; namespace SelectSort < class Program < static void Main(string[] args) < Console.WriteLine("Введите через запятую целые числа и нажмите Enter"); string[] nums = Console.ReadLine().Split(new char[] < ',' >); int[] intArray = new int[nums.Length]; for (int i = 0; i < nums.Length; i++) < intArray[i] = int.Parse(nums[i]); >Console.WriteLine("Неотсортированный массив:"); foreach (int value in intArray) < Console.Write($""); > int indx; //переменная для хранения индекса минимального элемента массива for (int i = 0; i < intArray.Length; i++) //проходим по массиву с начала и до конца < indx = i; //считаем, что минимальный элемент имеет текущий индекс for (int j = i; j < intArray.Length; j++) //ищем минимальный элемент в неотсортированной части < if (intArray[j] < intArray[indx]) < indx = j; //нашли в массиве число меньше, чем intArray[indx] - запоминаем его индекс в массиве >> if (intArray[indx] == intArray[i]) //если минимальный элемент равен текущему значению - ничего не меняем continue; //меняем местами минимальный элемент и первый в неотсортированной части int temp = intArray[i]; //временная переменная, чтобы не потерять значение intArray[i] intArray[i] = intArray[indx]; intArray[indx] = temp; > Console.WriteLine("\r\nОтсортированный массив:"); foreach (int value in intArray) < Console.Write($""); > > > >
Также, Вы можете загрузить исходный код приложения из нашего репозитория на Github.
Итого
Сегодня мы написали своё первое полноценное приложение на C# для сортировки массива. Как видите, для этого нам пригодилось всё, что мы изучали ранее — переменные, работа с массивами, литералы, циклы и так далее. Постепенно, наши программы будут «обрастать» новыми возможностями, станут более устойчивыми к различным ситуациям (например, сегодня я даже не пытался проверить то, что ввел пользователь, хотя такую проверку необходимо проводить). Но всё это будет делаться постепенно, по мере изучения возможностей C#.
уважаемые посетители блога, если Вам понравилась, то, пожалуйста, помогите автору с лечением. Подробности тут.