4A. Sortowanie bąbelkowe i przez wstawianie

FilmProgramowanie w C++. Sortowanie przez wstawianie

Film omawia sortowanie przez wstawianie oraz procedurę wstawiania danego elementu do posortowanej tablicy i jej realizację w C++.

Ćwiczenie 0

Zdefiniuj funkcję trzy(int a, int b, int c), której wynikiem jest największa z trzech liczb podanych jako parametr. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji trzy(1, 9, 12) jest 12.
Wynikiem funkcji trzy(13, 4, 12) jest 13.

Wskazówka
Na początku za największą liczbę przyjmuje się pierwszą z trzech podanych jako parametr. Następnie bada się, czy druga z liczb nie jest większa od niej, jeśli tak, to za największą przyjmuje się drugą liczbę. Następnie bada się, czy trzecia z liczb nie jest większa od niej, jeśli tak, to za największą przyjmuje się trzecią liczbę.

#include <iostream>
using namespace std;

int trzy(int a, int b, int c) {
	//zdefiniuj funkcję i sprawdź jej działanie

Wynikiem funkcji trzy(10, 10, 10) jest 10

return trzy(10, 10, 10)==10;

10

trzy(10, 10, 10)

Wynikiem funkcji trzy(112, 99, 112) jest 112

return trzy(112, 99, 112)==112;

112

trzy(112, 99, 112)

Wynikiem funkcji trzy(456, 456, 455) jest 456

return trzy(456, 456, 455)==456;

456

trzy(456, 456, 455)

Rozwiąż ćwiczenie

Ćwiczenie 1Losowa tablica liczb

Zdefiniuj funkcję losuj(int a, int b) służącą do generowania wartości losowych z podanego zakresu <a, b> i zapisywania ich w 25-elementowej tablicy, oraz funkcję wypisz(), która będzie wypisywała wszystkie elementy tablicy.

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

void losuj(int a, int b) {
	//zdefiniuj funkcję i sprawdź jej działanie

Rozwiąż ćwiczenie

Ćwiczenie 2Bąbelek

Porównaj kolejne pary elementów tablicy (pierwszy z drugim, drugi z trzecim itd.). Jeśli pierwszy z nich jest większy niż drugi, to zamień je miejscami. Przeanalizuj podane niżej wyniki (czy widzisz pewną prawidłowość w wynikowej tablicy?) i zdefiniowaną funkcję babelek(), po wywołaniu której zostanie zmodyfikowana dana tablica liczb. Następnie znajdź i popraw błąd w funkcji oraz sprawdź działanie programu dla podanych parametrów.

Wynikiem funkcji dla int tab[5] = {16, 5, 12, 3, 12} jest {5, 12, 3, 12, 16}.
Wynikiem funkcji dla int tab[7] = {1, 16, 18, 3, 16, 9, 9} jest {1, 16, 3, 16, 9, 9, 18}.

#include <iostream>
using namespace std;

const int N = 7;
int tab [N] = {1, 16, 18, 3, 16, 9, 9};

void wypisz() {
	for (int i = 0; i < N; i++)
		cout << tab[i] << " ";
	cout << endl;
}

void babelek() {
	for (int i = 0; i < N - 1; i++)
		if (tab[i] < tab[i + 1]) swap(tab[i], tab [i + 1]);
}

int main() {
	wypisz();
	babelek();
	wypisz();
	return 0;
}

Rozwiąż ćwiczenie

Ćwiczenie 3Sortowanie bąbelkowe

Zdefiniuj funkcję sort_b(), po wywołaniu której dana tablica liczb zostanie posortowana metodą bąbelkową w porządku rosnącym. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji dla int tab[N] = {6, 3, 15, 9, 2} jest {2, 3, 6, 9, 15}.
Wynikiem funkcji dla int tab[N] = {11, 16, 8, 33, 6, 8, 1} jest {1, 6, 8, 8, 11, 16, 33}.

#include <iostream>
using namespace std;

void sort_b() {
	//zdefiniuj funkcję i sprawdź jej działanie

Rozwiąż ćwiczenie

Ćwiczenie 5Wstawianie elementów

Zdefiniuj funkcję wstawianie(int x), której parametrem jest liczba wstawiająca odpowiednio liczbę x do posortowanej tablicy. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji dla int tab[N] = {6, 13, 15, 19, 22, 0} i wstawianie(18) jest {6, 13, 15, 18, 19, 22}.
Wynikiem funkcji dla int tab[N] = {1, 9, 12, 33, 46, 0} i wstawianie(57) jest [1, 9, 12, 33, 46, 57].

#include <iostream>
using namespace std;

void wstawianie(int x) {
	//zdefiniuj funkcję i sprawdź jej działanie

Rozwiąż ćwiczenie

Ćwiczenie 6Sortowanie przez wstawianie

Uzupełnij definicję funkcji sort_w(), po uruchomieniu której tablica tab zostanie posortowana metodą przez wstawianie w porządku rosnącym. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji int tab[N] = {6, 3, 15, 9, 2} jest {2, 3, 6, 9, 15}.
Wynikiem funkcji int tab[N] = {11, 16, 8, 33, 6, 8, 1} jest {1, 6, 8, 8, 11, 16, 33}.

#include <iostream>
using namespace std;

const int N = 7;
int tab[N] = {11, 16, 8, 33, 6, 8, 1};

void sort_w() {
	for(int j = N - 2; j >= 0; j--) {
		int x = tab[j];
		int i = j + 1;
		while((i < N) and (x > tab[i])) {
			tab[i - 1] = tab[i];
			i++;
		}
		tab[i - 1] = x;
	}
}

Rozwiąż ćwiczenie

Zadanie 1Sortowanie bąbelkowe – wersja uproszczona

Zdefiniuj funkcję sort_b2(), w wyniku której dana tablica t zostanie posortowana uproszczoną metodą bąbelkową.

#include <iostream>
using namespace std;

void sort_b2() {
	//zdefiniuj funkcję i sprawdź jej działanie

Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 1

Zdefiniuj funkcję minimum(int liczba), której wynikiem będzie najmniejsza cyfra liczby podanej jako parametr. Parametrem jest co najmniej dwucyfrowa liczba całkowita dodatnia. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem minimum(19) jest 1.
Wynikiem minimum(98989) jest 8.

#include <iostream>
using namespace std;

int minimum(int liczba) {
	//zdefiniuj funkcję i sprawdź jej działanie

Wynikiem funkcji minimum(777777777) jest 7

return minimum(777777777)==7;

7

minimum(777777777)

Wynikiem funkcji minimum(9876543210) jest 0

return minimum(9876543210)==0;

0

minimum(9876543210)

Wynikiem funkcji minimum(12345678987654321) jest 1

return minimum(12345678987654321)==1;

1

minimum(12345678987654321)

Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 2

Zdefiniuj funkcję ile_liczb(), której wynikiem jest liczba różnych liczb w tablicy podanej jako parametr. Parametrem jest niepusta tablica co najwyżej 100 liczb z zakresu od 0 do 10. Sprawdź działanie funkcji dla podanych poniżej parametrów.

Wynikiem funkcji ile_liczb() dla tablicy {4, 1, 1, 4} jest 2.
Wynikiem funkcji ile_liczb() dla tablicy {6, 6, 3, 7, 1, 7, 4, 4, 0, 3} jest 6.

#include <iostream>
using namespace std;

int ile_liczb() {
	//zdefiniuj funkcję i sprawdź jej działanie

Rozwiąż ćwiczenie

Informatyka 2